#include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <vector>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <string>

 #include <set>

 #include <functional>

 #include <numeric>

 #include <sstream>

 #include <stack>

 #include <map>

 #include <queue>

 #include <deque>

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #define CL(arr, val)    memset(arr, val, sizeof(arr))

 #define ll long long

 #define INF 0x7f7f7f7f

 #define lc l,m,rt<<1

 #define rc m + 1,r,rt<<1|1

 #define pi acos(-1.0)

 #define L(x)    (x) << 1

 #define R(x)    (x) << 1 | 1

 #define MID(l, r)   (l + r) >> 1

 #define Min(x, y)   (x) < (y) ? (x) : (y)

 #define Max(x, y)   (x) < (y) ? (y) : (x)

 #define E(x)        (1 << (x))

 #define iabs(x)     (x) < 0 ? -(x) : (x)

 #define OUT(x)  printf("%I64d\n", x)

 #define lowbit(x)   (x)&(-x)

 #define Read()  freopen("a.txt", "r", stdin)

 #define Write() freopen("b.txt", "w", stdout);

 #define maxn 1010

 #define maxv 1010

 #define mod 1000000000

 using namespace std;

 struct edge

 {

     int to,weight;

 };

 vector<edge>adjmap[maxn]; //动态邻接表

 bool in_queue[maxn]; //顶点是否在队列中

 int in_sum[maxn];//顶点入队次数

 int dist[maxn];//源点到各点的最短路径

 int path[maxn]; //存储到达i的前一个顶点

 int nodesum; //顶点数

 int edgesum; //边数

 bool SPFA(int source)

 {

     deque<int>dq;

     int i,j,x,to;

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

     {

         in_sum[i]=;

         in_queue[i]=false;

         dist[i]=INF;

         path[i]=-;

     }

     dq.push_back(source);

     in_sum[source]++;

     dist[source]=;

     in_queue[source]=true;

     //初始化 完成

     while(!dq.empty())

     {

         x=dq.front();  //取出队首元素

         dq.pop_front();

         in_queue[x]=false; //访问标记置0 ,同一个顶点可以访问多次,只要dist值变小

         for(i=;i<adjmap[x].size();i++)

         {

             to=adjmap[x][i].to;

             if((dist[x]<INF)&&(dist[to]>dist[x]+adjmap[x][i].weight))

             {

                 dist[to]=dist[x]+adjmap[x][i].weight;

                 path[to]=x;  //记录路径

                 if(!in_queue[to])

                 {

                     in_queue[to]=true;

                     in_sum[to]++;  //访问次数加1

                     if(in_sum[to]==nodesum) return false; //访问次数等于 顶点数 存在负权回路

                     if(!dq.empty())

                     {

                         if(dist[to]>dist[dq.front()]) dq.push_back(to); //大的加入 队尾

                         else dq.push_front(to); //小的加入队首

                     }

                     else dq.push_back(to); //队列为空加入队尾

                 }

             }

         }

     }

 }

 void Prit_Path(int x)

 {

     stack<int>s;

     int w=x;

     while(path[w]!=-)  //用栈保存路径

     {

         s.push(w);

         w=path[w];

     }

     cout<<"顶点1到顶点"<<x<<"最短路径长度为:"<<dist[x]<<endl;

     cout<<"所经过的路径为:1 ";

     while(!s.empty())

     {

         cout<<s.top()<<" ";

         s.pop();

     }

     cout<<endl;

 }

 int main()

 {

     freopen("a.txt","r",stdin);

     int i,s,e,w;

     edge temp;

    // cout<<"输入顶点数和边数：";

     cin>>nodesum>>edgesum;

     for(int i=;i<=nodesum;i++) adjmap[i].clear();

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

     {

        // cout<<"输入第"<<i<<"条边的起点,终点还有对应的权值:";

         cin>>s>>e>>w;

         temp.to=e;

         temp.weight=w;

         adjmap[s].push_back(temp);

     }

     if(SPFA())

     {

         for(int i=;i<=nodesum;i++) Prit_Path(i);

     }

     else cout<<"图中存在负权回路"<<endl;

     return ;

 }