#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

queue <int> Q;
vector <pair<int,int> > nod[50500];
int dist[50500], visit[50500];
int n, m, i, x, y, c, go_to, now;

int main()
{
    fin>>n>>m;
    for ( i=1 ; i<=m ; i++ )
    {
        fin>>x>>y>>c;
        nod[ x ].push_back(make_pair(y,c));
    }

    Q.push(1);
    visit[1]=1;
    while ( !Q.empty() )
    {
        now=Q.front(); Q.pop();
        go_to=nod[ now ].size();
        for ( i=0 ; i<go_to ; i++ )
        {
            if ( visit[ nod[ now ][ i ].first]==0 || dist[ nod[ now ][ i ].first]>dist[ now ]+nod[ now ][ i ].second )
            {
                Q.push( nod[ now ][ i ].first );
                dist[ nod[ now ][ i ].first ] = dist[ now ] + nod[ now ][ i ].second;
                visit[ nod[ now ][ i ].first ]=1;
            }
        }

    }

    for ( i=2 ; i<=n ; i++ )
        fout<<dist[i];

    return 0;
}