#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> int_pair;

const int MAX = 50001;
const int INF = 0x3f3f3f3;

int n,m;
vector<int_pair>graph[MAX];

void read(){
    scanf("%d %d",&n,&m);

    for(int i=0;i<m;++i){
        int start,end,cost;
        scanf("%d %d %d",&start,&end,&cost);
        graph[start].push_back(make_pair(end,cost));
    }
}

void relax(int v,int u, int w ,vector<int> &dist,priority_queue<int_pair,vector<int_pair>,greater<int_pair>> &pq){
    if(dist[v]>dist[u]+w){
        dist[v]=dist[u]+w;
        pq.push(make_pair(dist[v],v));
    }
}

void dij(){
    priority_queue<int_pair,vector<int_pair>,greater<int_pair>> pq;
    vector<int>dist(n+1,INF);

    pq.push(make_pair(0,1));
    dist[1]=0;

    while (!pq.empty()){
        int u= pq.top().second;
        pq.pop();
        for(auto i:graph[u]){
            int v = i.first;
            int w = i.second;
            relax(v,u,w,dist,pq);
        }
    }
    for(int i=2;i<=n;++i){
        printf("%d ",dist[i]);
    }
}

int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    read();
    dij();

}