#include <bits/stdc++.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct edge{
    int vec;
    int cost;
    bool operator<(const edge &a) const{
        return cost>a.cost;
    }
};
vector<edge> V[50001];
priority_queue<edge> q;
int d[50001],n,m;
void dijkstra(int nod){
    q.push({nod,0});
    for(int i=0;i<=n;i++){
        d[i]=INT_MAX;
    }
    while(!q.empty()){
        edge aux=q.top();
        q.pop();
        int nod=aux.vec,cost=aux.cost;
        if(d[nod]==INT_MAX ){
            d[nod]=cost;
            for(int i=0;i<V[nod].size();i++){
                if(d[V[nod][i].vec]==INT_MAX){
                    q.push({V[nod][i].vec,V[nod][i].cost+cost});
                }
            }
        }
    }
}
int main()
{
    f>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;
        f>>a>>b>>c;
        V[a].push_back({b,c});
    }
    dijkstra(1);
    for(int i=2;i<=n;i++){
        if(d[i]==INT_MAX){
            g<<"0 ";
        }else{
            g<<d[i]<<" ";
        }
    }
    return 0;
}