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

using namespace std;

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

int main ()
{
    int N, M; f >> N >> M;

    vector < pair<int,int> > v[N];
    for (int i = 0; i < M ; ++i) {
        int x, y, c; f >> x >> y >> c;
        --x; --y;
        v[x].push_back(make_pair(y, c));
    }

    vector <int> D(N,0x3f3f3f3f);
    priority_queue < pair<int,int> > pq;
    vector <bool>  viz(N);

    D[0] = 0;
    pq.push(make_pair(0,0));

    while(1)
    {
        while(!pq.empty() && viz[pq.top().second])
            pq.pop();
        if(pq.empty())
            break;
        int x = pq.top().second;
        viz[x]=1;
        pq.pop();

        for (auto &it : v[x])
            if(D[x] + it.second < D[it.first]) {
                D[it.first] = D[x] + it.second;
                pq.push(make_pair(-D[it.first], it.first));
            }
    }

    for(int i = 0; i < N; ++i)
        if(D[i] == 0x3f3f3f3f)
            D[i] = 0;
    for(int i = 1; i < N; ++i)
        g << D[i] << " ";

    return 0;
}