#include <bits/stdc++.h>

using namespace std;
const int INF = 100000;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
vector<pair<int,int>> graf[100005];
int n,m,dist[100005],parent[100005],viz[100005];
int main()
{
    in>>n>>m;
    for (int i=0;i<n;i++){
        dist[i] = INF;
        parent[i] = -1;
    }

    for(int i=0;i<m;i++)
    {
        int a,b,c;
        in>>a>>b>>c;
        graf[a-1].push_back({b-1,c});
    }
    dist[0] = 0;
    pq.push({0,0});
    while(!pq.empty())
    {
        int x = pq.top().second;
        pq.pop();
        if(viz[x])
            continue;
        viz[x] = 1;
        for (auto it:graf[x])
        {
            int v = it.first;
            int weight = it.second;
            if (dist[v] > dist[x] + weight)
            {
                dist[v] = dist[x] + weight;
                parent[v] = x;

                pq.push(make_pair(dist[v], v));
            }
        }
    }
    for (int i=1;i<n;i++)
        if(dist[i] == INF)
            out<<0;
        else
            out<<dist[i]<<' ';
}