#include <fstream>
#include <vector>
#include <bitset>
#include <queue>

#define f first
#define s second
#define pb push_back

using namespace std;

ifstream F("dijsktra.in");
ofstream G("dijsktra.out");

int n, m, x, y, c, d[ 50005 ];
vector<pair<int, int> > a[ 50005 ];
priority_queue<pair<int, int> > pq;
bitset<50005> w;
const int inf = 1 << 30;

int main()
{
    F >> n >> m;
    for( int i = 1; i <= m; ++ i )
    {
        F >> x >> y >> c;
        a[ x ].pb( { y, c } );
    }
    for( int i = 2; i <= n; ++ i ) d[ i ] = inf;
    pq.push( { 0, 1 } );
    vector<pair<int, int> > :: iterator it;
    while( !pq.empty() )
    {
        x = pq.top().s;
        pq.pop();
        if( w[ x ] ) continue;
        w[ x ] = 1;
        for( it = a[ x ].begin(); it != a[ x ].end(); ++ it )
            if( d[ (*it).f ] > d[ x ] + (*it).s )
                d[ (*it).f ] = d[ x ] + (*it).s, pq.push({ -d[ (*it).f ], (*it).f });
    }
    for( int i = 2; i <= n; ++ i )
        d[ i ] == inf ? G << 0 << " " : G << d[ i ] << " ";
    return 0;
}