#include <bits/stdc++.h>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector<pair<int, int>> adj[50005];
int N, M;
int dist[50005];
int main()
{
    f >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        dist[i] = 1000000000;
    }
    for (int i = 1; i <= M; i++)
    {
        int x, y, z;
        f >> x >> y >> z;
        adj[x].push_back({y, z});
    }
    priority_queue<pair<int, int>> pq;
    pq.push({0, 1});
    dist[1] = 0;
    while (!pq.empty())
    {
        int crtNode = pq.top().second;
        pq.pop();
        for (int i = 0; i < adj[crtNode].size(); i++)
        {
            int vecin = adj[crtNode][i].first;
            int cost = adj[crtNode][i].second;
            if (dist[crtNode] + cost < dist[vecin])
            {
                dist[vecin] = dist[crtNode] + cost;
                pq.push({-dist[vecin], vecin});
            }
        }
    }
    for (int i = 2; i <= N; i++)
    {
        if(dist[i] == 1000000000){
            g<<0<<" ";
        }
        else{
            g<<dist[i]<<" ";
        }
    }
}