#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

vector < pair<int,int> >v[50001];
priority_queue <int>q;
int dist[50001];

int main()
{
    freopen( "dijkstra.in", "r", stdin );
    freopen( "dijkstra.out", "w", stdout );
    int n, m, i, x, y, z;
    scanf( "%d%d", &n, &m );
    for( i=2; i<=n; ++i )dist[i]=1000000;
    for( i=1; i<=m; ++i )
    {
        scanf( "%d%d%d", &x, &y, &z );
        v[x].push_back( {y,z} );
    }
    q.push(1);
    while( !q.empty() )
    {
        x=q.top(),q.pop();
        for( size_t i=0; i<v[x].size(); ++i )
            if( dist[v[x][i].first]>dist[x]+v[x][i].second )
            {
                dist[v[x][i].first]=dist[x]+v[x][i].second;
                q.push(v[x][i].first);
            }
    }
    for( i=2; i<=n; ++i )
        if( dist[i]==0x3f3f3f3f )printf("0 ");
        else printf( "%d ", dist[i] );
    return 0;
}