#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <climits>
#define lim 2147483647
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,k,c,drum[50001];
vector<pair<int,int>> l[50001];
set< pair<int,int> > setul;
int main(){
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>j>>k>>c;
        l[j].push_back(make_pair(k,c));
    }
    for(int i=2;i<=n;i++)
        drum[i]=lim;
    drum[1]=0;
    setul.insert(make_pair(0,1));
    set<pair<int,int>>::iterator it;
    while(!setul.empty()){
        k=setul.begin()->y;
        setul.erase(setul.begin());
        for(int i=0;i<l[k].size();i++){
            int nbg=l[k][i].first,cost=l[k][i].second;
            if(drum[nbg]>drum[k]+l[k][i].second){
                setul.erase(make_pair(drum[nbg],nbg));
                drum[nbg]=drum[k]+l[k][i].second;
                setul.insert(make_pair(drum[k]+l[k][i].second,nbg));
            }
        }
    }
    for(int i=2;i<=n;i++)
        if(drum[i]==lim)
            fout<<"0 ";
        else
            fout<<drum[i]<<" ";

}