#include <fstream>
#include <set>
#include <vector>
#define INF 1000000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,x,y,c,i,nod,vecin,cost,d[50002];
vector <pair<int,int> > v[50002];
set <pair<int,int> > s;
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>c;
        v[x].push_back({y,c});
    }
    for(int i=2;i<=n;d[i]=INF,i++);
    s.insert({0,1}); //s continte (d[nod], nod)

    while(!s.empty()){
        nod=s.begin()->second;
        s.erase(s.begin());
        for(i=0;i<v[nod].size();i++){
            vecin=v[nod][i].first;
            cost=v[nod][i].second;
            if(d[nod]+cost<d[vecin]){
                s.erase({d[vecin],vecin}); //sterg perechea veche daca exista
                d[vecin]=cost+d[nod];
                s.insert({d[vecin],vecin}); //adaug percehea mai optima
            }
        }
    }
    for(i=2;i<=n;i++)
        if(d[i]!=INF)fout<<d[i]<<" ";
        else fout<<"0 ";
    return 0;
}