#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int N_MAX = 5e4 + 5;

int N, M;
int u, v, c;

vector < pair < int, int > > G[N_MAX];
int dist[N_MAX];

void Dijkstra(int startNode)
{
    priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > PQ;
    int vis[N_MAX] = {0};
    int currNode, currCost, node, cost;

    PQ.push(make_pair(0, startNode));

    while (PQ.size())
    {
        do
        {
            currNode = PQ.top().second;
            currCost = PQ.top().first;
            PQ.pop();
        }while (PQ.size() && vis[currNode] == 1);

        vis[currNode] = 1;

        for (int i = 0; i < G[currNode].size(); i++)
        {
            node = G[currNode][i].first;
            cost = G[currNode][i].second;
            if (dist[node] > currCost + cost && vis[node] == 0)
            {
                dist[node] = currCost + cost;
                PQ.push(make_pair(dist[node], node));
            }
        }
    }
}

int main()
{
    fin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        fin >> u >> v >> c;
        G[u].push_back(make_pair(v, c));
    }
    for (int i = 1; i <= N; i++)
        dist[i] = INT_MAX;
    Dijkstra(1);
    for (int i = 2; i <= N; i++)
        if (dist[i] == INT_MAX)
            fout << "0 ";
        else
            fout << dist[i] << " ";
    return 0;
}