// 路径还原

 // 求最短路，并输出最短路径

 // 在单源最短路问题中我们很容易想到，既然有许多条最短路径，那将之都存储下来即可

 // 但再想一下，我们是否要把所有的最短路径都求出来呢？

 // 实际上不需要，这里我们用一个数组来记录最短路径，之后的最短路径都是在之前最短路径上的延申

 // 所以只需要一个数组，存储前一个节点即可

 // 这里我们用邻接表和优先级队列来实现复杂度为o( E*log(N) )的Dijkstra算法

 #include <cstdio>

 #include <iostream>

 #include <queue>

 #include <vector>

 using namespace std;

 const int max_N = +;

 const int max_E = +;

 const int INF = 1e9;

 int N,E,S;

 int d[max_N];

 int pre[max_N];

 struct edge

 {

     int to,cost;

 };

 edge es[max_N];

 vector<edge> G[max_N];

 typedef pair<int,int> P;

 void Dijkstra(int s)

 {

     pre[s]=-;

     fill(d,d+N,INF);

     d[s]=;

     // 实现最小堆

     priority_queue< P,vector<P>,greater<P> > que;

     que.push(P(,s));

     while(!que.empty())

     {

         // 非空时，取出一个顶点

         P p=que.top();

         que.pop();

         // 当前节点的编号是v,队列中记录的到当前节点的最短距离是p.first

         int v=p.second;

         // 如果当前节点的最小值，小于数组中记录的最小值的话

         // 说明当前节点的最小值已经被覆盖过了，这个节点是无效节点，继续下一次循环

         if(d[v]<p.first)

         {

             continue;

         }

         for(int i=;i<G[v].size();++i)

         {

             edge e=G[v][i];

             if(d[e.to]>d[v] + e.cost)

             {

                 d[e.to]=d[v]+e.cost;

                 pre[e.to]=v;

                 que.push(P( d[e.to],e.to ));

             }

         }

     }

 }

 void path(int i)

 {

     if(i==S)

     {

         printf("start:%d\n",S);

         return;

     }

     vector<int> p;

     for(;i!=-;i=pre[i])

     {

         p.push_back(i);

     }

     vector<int>::iterator it;

     for(it=p.end()-;it!=p.begin()-;--it)

     {

         cout<<*it<<' ';

     }

     cout<<endl;

 }

 int main()

 {

     scanf("%d %d",&N,&E);

     int a,b,c;

     for(int i=;i<E;++i)

     {

         scanf("%d %d %d",&a,&b,&c);

         edge e;

         e.to=b;

         e.cost=c;

         G[a].push_back(e);

         // 无向图

         e.to=a;

         e.cost=c;

         G[b].push_back(e);

     }

     // 起点为0号节点

     S=;

     Dijkstra(S);

     for(int i=;i<N;++i)

     {

         printf("%d ",d[i]);

     }

     printf("\n\n");

     for(int i=;i<N;++i)

     {

         path(i);

     }

     return ;

 }

 /*

 7 10

 0 1 2

 0 2 5

 1 2 4

 1 3 6

 1 4 10

 2 3 2

 3 5 1

 4 5 3

 4 6 5

 5 6 9

 */