#include <queue>
#include <vector>
#include <fstream>
using namespace std;

#define MAXN 50100
#define INF 1000000000

int N, M, d[MAXN]; vector<pair<int,int> > v[MAXN];
priority_queue< pair<int, int> > T;

void solve(void)
{
    int i, j, k, val, x;

    for(i = 2; i <= N; i++) d[i] = INF;
    T.push( make_pair(1, 0) );

    while( T.size() > 0 )
    {
        i = T.top().first, val = T.top().second;
        T.pop();
        for(j = 0; j < v[i].size(); j++)
         if(d[ v[i][j].first ] > val + v[i][j].second )
            d[ v[i][j].first ] = val + v[i][j].second, T.push(make_pair(v[i][j].first,d[v[i][j].first]));
    }
}

int main(void)
{
   ifstream f("dijkstra.in");
   ofstream g("dijkstra.out");

    int i, a, b, c;

    f>>N>>M;

    for(i = 1; i <= M; i++)
        f>>a>>b>>c, v[a].push_back(make_pair(b,c));

    solve();

    for(i = 2; i <= N; i++)
        if(d[i]!=INF) g<<d[i]<<" ";
        else g<<0<<" ";

f.close();
g.close();

    return 0;
}