#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef list<ii> lii;

void Dijkstra(vector<lii> &G, int n, int start, vector<int> &dist)
{
    dist[start] = 0;
    priority_queue<ii, vector<ii>, greater<ii> > pq;
    pq.push(ii(0,start));
    while(!pq.empty())
    {
        ii frt = pq.top();
        pq.pop();
        int d = frt.first;
        int nod = frt.second;
        if(d <= dist[nod])
            for(ii p : G[nod])
            {
                int v = p.first;
                d = p.second;
                if(dist[nod] + d < dist[v])
                {
                    dist[v] = dist[nod] + d;
                    pq.push(ii(dist[v],v));
                }
            }
    }

    for(int i=1; i<=n; i++)
        if(dist[i] == INT_MAX)
            dist[i] = 0;
}
int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    int n, m, u, v, cost;
    vector<lii> G;
    in>>n>>m;
    G.resize(n+1);
    for(int i=1; i<=m; i++)
    {
        in>>u>>v>>cost;
        G[u].push_back(make_pair(v,cost));
       // G[v].push_back(make_pair(u,cost));
    }
    vector<int> dist;
    dist.resize(n+1,INT_MAX);
    Dijkstra(G, n, 1, dist);
    for(int i=2; i<=n; i++)
        out<<dist[i]<<'\n';
    return 0;
}