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

using namespace std;

vector < pair<int,int> >v[500005];
queue <int>q;
bool w[500005];
int dist[500005];

int main()
{
    freopen( "bellmanford.in", "r", stdin );
    freopen( "bellmanford.out", "w", stdout );
    int n, m, i, x, y, z;
    scanf( "%d%d", &n, &m );
    for( i=2; i<=n; ++i )dist[i]=0x3f3f3f3f;
    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.front();q.pop();w[x]=0;
        for( auto vec : v[x] )
            if( dist[vec.first]>dist[x]+vec.second )
            {
                dist[vec.first]=dist[x]+vec.second;
                if( !w[vec.first] )
                {
                    q.push(vec.first);
                    w[x]=1;
                }
            }
    }
    for( i=2; i<=n; ++i )
        if( dist[i]==0x3f3f3f3f ) printf("0 ");
        else printf( "%d ", dist[i] );
    return 0;
}