#include <bits/stdc++.h>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define dist first
#define poz second

vector <pair < int, int > > adj[50001];
priority_queue <pair < int, int > > pq;

int main()
{
    int dist[50001];
    int n, m;
    f >> n >> m;
    for ( int i = 1; i <= m; i ++ )
    {
        int x, y, z;
        f >> x >> y >> z;
        adj[x].push_back( {z, y} );
    }
    for ( int i = 0; i <= n; i ++ )
        dist[i] = INT_MAX;
    dist[1] = 1;
    pq.push( { - 1, 1 } );
    while ( pq.size() )
    {
        int c = pq.top().poz;
        int temp = pq.top().dist;
        int ggwp = dist[c];
        pq.pop();
        if ( -1 * temp <= ggwp )
        {
            for ( int i = 0; i < adj[c].size(); i ++ )
            {
                pair <int, int> l = adj[c][i];
                if ( dist[c] + l.dist < dist[l.poz] )
                {
                    dist[l.poz] = dist[c] + l.dist;
                    pq.push( { - dist[l.poz], l.poz } );
                }
            }
        }
    }
    for ( int i = 2; i <= n; i ++ )
    {
        if ( dist[i] == INT_MAX)
            g << 0 << " ";
        else g << dist[i] - 1 << " ";
    }
    return 0;
}