#include <bits/stdc++.h>
#define NMax 50003
#define oo 1<<30

using namespace std;

priority_queue< pair<int, int> > q;
vector< pair<int, int> > L[NMax];
int viz[NMax];
int d[NMax];
int N, M;

int main()
{
    ifstream fin("dijkstra.in");

    int i, k, C, x, y;
    unsigned int j;
    fin >> N >> M;
    for(i = 1; i <= M; ++i)
    {
        fin >> x >> y >> C;
        L[x].push_back({y, C});
    }

    for(i = 2; i <= N; i++) d[i] = oo;
    q.push({0, 1}); // pun perechi (cost, nod)
    while(!q.empty())
    {
        k = q.top().second;
        q.pop();
        if(!viz[k])
        {
            viz[k] = 1;
            for(auto w : L[k])
            {
                i = w.first;
                C = w.second;
                if(d[i] > d[k] + C)
                {
                    d[i] = d[k] + C;
                    q.push({-d[i], i});
                }
            }
        }
    }

    ofstream fout("dijkstra.out");
    for(i = 2; i <= N; ++i)
        if(d[i] != oo) fout << d[i] << " ";
        else fout << "0 ";

    fout.close();
    return 0;
}