#include <iostream>#include <cstdlib>#include <cstdio>#include <algorithm>#include <vector>#include <queue>#include <cmath>#include <cstring>using namespace std;#define INF 0xfffffff#define maxn 40struct Edge{    int e, w;    Edge(int e=0,int w=0) : e(e), w(w) {}};int Path[maxn], n, dist[maxn];bool vis[maxn];vector<Edge> G[maxn];void Spfa(int Star,int End){    Edge P, Pn;    dist[Star] = 0;    queue<Edge> Q;    Q.push(Edge(Star,0));    while( !Q.empty() )    {        P = Q.front();        Q.pop();        vis[P.e] = true;        int len = G[P.e].size();        for(int i=0; i<len; i++)        {            Pn = G[P.e][i];            if(dist[Pn.e] > dist[P.e] + Pn.w)            {                dist[Pn.e] = dist[P.e] + Pn.w;                Path[Pn.e] = P.e;                if( !vis[Pn.e] )                {                    Q.push(Pn);                    vis[Pn.e] = true;                }            }        }    }}void PutPath(int Star,int End){    if(Star == End)    {        printf("%d", Star);        return ;    }    PutPath(Star, Path[End]);    printf("---->%d", End);}void Init(){    for(int i=1; i<=n; i++)    {        G[i].clear();        dist[i] = INF;        vis[i] = false;        Path[i] = i;    }}int main(){    int m;    cin >> n >> m;    Init();    for(int i=1; i<=m; i++)    {        int a, b, c;        cin >> a >> b >> c;        G[a].push_back(Edge(b,c));    }    Spfa(1, n);    printf("%d\n", dist[n]);    PutPath(1,n);    return 0;}/*4 31 2 12 3 13 4 1*/