#include<iostream>
#include<fstream>
#include<vector>
#include<list>
#include<limits.h>
using namespace std;
struct nod{
int dist;
vector<nod*> next;
vector<int> lng;};
nod*nnod(){
    nod*dummy;
    dummy=new nod;
    dummy->dist=INT_MAX;
    return dummy;}
bool cmp(nod*a,nod*b){
return (a->dist<b->dist);}
void dijkstra(vector<nod*> &vect){
    int v_min;
    nod*n_min;
    list<nod*> lst;
    lst.push_back(vect[0]);
    vect[0]->dist=0;
    while(lst.size()!=0){
        v_min=INT_MAX;
        //for(list<nod*>::iterator i=lst.begin();i!=lst.end();i++)if((*i)->dist<v_min){v_min=(*i)->dist;n_min=(*i);}
        lst.sort(cmp);
        n_min=*lst.begin();
        while(*lst.begin()==n_min)lst.pop_front();
        for(int i=0;i<n_min->next.size();i++){
        if(n_min->lng[i]+n_min->dist<n_min->next[i]->dist)n_min->next[i]->dist=n_min->lng[i]+n_min->dist;
        lst.push_back(n_min->next[i]);}}}
int main(){
    int n,m,a,b,c;
    vector<nod*> v;
    ifstream f("dijkstra.in");
    f>>n>>m;
    for(int i=0;i<n;i++)v.push_back(nnod());
    for(int i=0;i<m;i++){
    f>>a>>b>>c;
    v[a-1]->next.push_back(v[b-1]);
    v[a-1]->lng.push_back(c);}
    dijkstra(v);
    ofstream g("dijkstra.out");
    for(int i=1;i<v.size();i++)g<<(v[i]->dist==INT_MAX ? 0 : v[i]->dist)<<' ';
    f.close();g.close();
return 0;}