#include <bits/stdc++.h>

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int NMAX=50005;
int n,m,dist[NMAX];
bool seen[NMAX];
struct edge{
    int node,cost;
    bool operator<(const edge&aux)const{
        return aux.cost<cost;
    }
};
vector<edge>g[NMAX];
priority_queue<edge>pq;
int main()
{
    in>>n>>m;
    for(int i=1,a,b,cost;i<=m;i++){
        in>>a>>b>>cost;
        g[a].push_back({b,cost});
    }
    pq.push({1,0});
    dist[1]=0;
    while(!pq.empty()){
        int node=pq.top().node,cost=pq.top().cost;
        pq.pop();
        seen[node]=1;
        dist[node]=cost;
        pq.pop();
        for(auto y:g[node]){
            if(seen[y.node]==0||dist[y.node]>dist[node]+dist[y].cost){
                pq.push({y.node,cost+y.cost});
                dist[y.node]=dist[node]+dist[y].cost;
                }
        }
    }
    for(int i=2;i<=n;i++)
        out<<dist[i]<<" ";
    return 0;
}