// Reads a weighted, directed graph from a file and
// then uses Sedgewick's code for sparse shortest path (Dijkstra's alg)

import java.util.Scanner;

public class SPTfile
{
  public static void main(String[] args)
  {
    Scanner sc=new Scanner(System.in);
    int v=sc.nextInt();
    int e=sc.nextInt();
    Graph G=new Graph(v,true);
    for (int i=0;i<e;i++)
      G.insert(new Edge(sc.nextInt(),sc.nextInt(),sc.nextDouble()));
    GraphSPT spt=new GraphSPT(G,0);

    for (int i=1;i<v;i++)
      if (spt.dist(i)==spt.maxWT)
        System.out.format("No path to vertex %d\n",i);
      else
        System.out.format("Vertex %d has pred %d at distance %f\n",
          i,(spt.pathR(i)).v(),spt.dist(i));
  }
}