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

#define nmax 50001
#define inf (1<<30)

using namespace std;

int n, m;
int x, y, c;
int cost[nmax];
vector < pair<int, int> > G[nmax];
queue < pair<int, int> > Q;

int main()
{

    ifstream fi("dijkstra.in");
    ofstream fo("dijkstra.out");

    fi >> n >> m;
    for (int i = 1; i <= m; i++)
        fi >> x >> y >> c,
        G[x].push_back(make_pair(y, c));

    cost[1] = 0;
    for (int nod = 2; nod <= n; nod++)
        cost[nod] = inf;

    Q.push(make_pair(1, 0)); // nod, costul minim de la nodul 1 pana la nodul 'nod'

    while (!Q.empty())
    {
        int currentNode = Q.front().first;
        int currentCost = Q.front().second;

        Q.pop();

        for (int i = 0; i < G[currentNode].size(); i++)
        {
            int neighbourNode = G[currentNode][i].first;
            int neighbourCost = G[currentNode][i].second;

            if (currentCost + neighbourCost < cost[neighbourNode])
            {
                cost[neighbourNode] = currentCost + neighbourCost;
                Q.push(make_pair(neighbourNode, cost[neighbourNode]));

            }

        }

    }

    for (int node = 2; node <= n; node++)
    {
        if (cost[node] == inf)
            cost[node] = 0;

        fo << cost[node] << " ";

    }

    fi.close();
    fo.close();

    return 0;
}