#include <bits/stdc++.h>
#define mp make_pair

using namespace std;

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

vector < pair<int, int> > G[50005];
priority_queue < pair <int, int>, vector<pair <int, int> >, greater<pair <int, int> > > H;
vector <pair <int, int> > sol;

long long cost;

int n, m, x, y, c, Min[50005], nr;

bool viz[50005];

int main()
{
    f >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        f >> x >> y >> c;
        G[x].push_back(mp(c,y));
    }

    for (int i = 2; i <= n; i++)
        Min[i] = -1;

    Min[1] = 0;

    for (int i = 0; i < G[1].size(); i++)
    {
        H.push(G[1][i]);
        Min[G[1][i].second] = G[1][i].first;
    }

    nr = G[1].size();

    while (nr != 0)
    {
        while (viz[H.top().second] == true)
        {
            H.pop();
        }

        viz[H.top().second] = true;
        int c = H.top().second;
        H.pop();
        nr--;

        for (int i = 0; i < G[c].size(); i++)
        {
            int j = G[c][i].second;
            if (Min[j] == -1)
            {
                nr++;
                Min[j] = Min[c] + G[c][i].first;
                H.push(mp(Min[j], j));
            }
            else if (Min[j] > Min[c] + G[c][i].first)
            {
                Min[j] = Min[c] + G[c][i].first;
                H.push({Min[j], j});
            }
        }
    }

    for (int i = 2; i <= n; i++)
        if (Min[i] == -1)
            g << 0 << ' ';
        else g << Min[i] << ' ';

    return 0;
}