#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");
    ofstream fout("dijkstra.out");

    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 });
    while (!q.empty())
    {
        k = q.top().second;
        q.pop();
        if (!viz[k])
        {
            viz[k] = 1;
            for (j = 0; j < L[k].size(); ++j)
            {
                i = L[k][j].first;
                C = L[k][j].second;
                if (d[i] > d[k] + C)
                {
                    d[i] = d[k] + C;
                    q.push({ -d[i], i });
                }
            }
        }
    }

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

    fout.close();
    return 0;
}