#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<pair<int,int>> v[10001];
int vizitat[10001],distanta[10001];
int n,m;
int main()
{
    fin>>n>>m;
    int x,y,w;
    while(fin>>x>>y>>w){
        v[x].push_back({y,w});
    }
    int inf=1000000;
    memset(distanta,inf,sizeof(distanta));
    distanta[1]=0;
    priority_queue<pair<int,int>> q;
    q.push({0,1});
    while(!q.empty()){
        int k=q.top().second;
        q.pop();
        if(vizitat[k]==0){
            vizitat[k]=1;
            for(auto element:v[k]){
                int i=element.first;
                int weight=element.second;
                if(distanta[i]>distanta[k]+weight){
                    distanta[i]=distanta[k]+weight;
                    q.push({-distanta[i],i});
                }
            }
        }
    }
    for(int i=1;i<=n;++i) {
        if(i!=1){
            fout<<distanta[i]<<" ";
        }
    }
    return 0;
}