#include <iostream>
#include <vector>
#include <set>
#include <climits>
#include <fstream>

using namespace std;

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

#define MAXN 50100

int N, M, d[MAXN];
vector<int> G[MAXN], C[MAXN];
set< pair<int, int> > T;

void solve()
{
    int i, j, k, val, x;
    for(i = 2; i <= N; i++)
        d[i] = INT_MAX;
    T.insert( make_pair(0, 1) );
    while( T.size() > 0 )
    {
        val = (*T.begin()).first, x = (*T.begin()).second;
        T.erase(*T.begin());
        for(i = 0; i < G[x].size(); i++)
            if(d[ G[x][i] ] > val + C[x][i] )
                d[ G[x][i] ] = val + C[x][i], T.insert(make_pair(d[G[x][i]],G[x][i]));
    }
}

int main(void)
{
    int i, a, b, c;
    f >> N >> M;
    for(i = 1; i <= M; i++)
        f >> a >> b >> c, G[a].push_back(b), C[a].push_back(c);
    solve();
    for(i = 2; i <= N; i++)
        if(d[i] == INT_MAX)
            g << 0 << " ";
        else
            g << d[i] << " ";
    return 0;
}