#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ft first
#define sc second
#define mp make_pair

typedef pair<int,int> iPair;
const int N_MAX = 50001;
const int INF = 0x3f3f3f3;

int n;
long m;

vector< pair<int,int> >graph[N_MAX];

void read(){
    scanf("%d %ld",&n,&m);
    for(long i=0;i<m;++i){
        int start,end,cost;
        scanf("%d %d %d",&start,&end,&cost);
        graph[start].pb(mp(end,cost) );
    }
}

void dijkstra(int src){
    priority_queue<iPair, vector<iPair>,greater<iPair> > minHeap;
    vector<int>dist(n+1,INF);
    
    minHeap.push(mp(0,src));
    dist[src]=0;
    while(!minHeap.empty()){
        int u=minHeap.top().sc;
        minHeap.pop();
        for(auto i:graph[u]){
            int v=i.ft;
            int cost = i.sc;
            if(dist[v]>dist[u]+cost){
                dist[v]=dist[u]+cost;
                minHeap.push(mp(dist[v],v));
            }
        }
    }
    
    for(int i=1;i<=n;++i){
        if(dist[i]!=0){
            printf("%d ",dist[i]);
        }
    }
}

int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    read();
    dijkstra(1);
    return 0;                
}