#include <bits/stdc++.h>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

#define Nmax 5054
#define pb push_back

const int INF=1e5;
int x,y,n,m,c1,L[Nmax];

vector <pair <int,int> > v[Nmax];
vector < int > T;

int cmp(const int&a, const int&b){
    return(L[a] > L[b]);
}

void dijkstra(){

    int node;
    T.pb(1);
    make_heap(T.begin(),T.end(),cmp);
     for(int i=2;i<=n;i++)
        L[i]=INF;
    while(!T.empty()){
        node=T.front();
        pop_heap(T.begin(),T.end(),cmp);
        T.pop_back();

        for(int i=0;i<v[node].size();i++){
            if(L[v[node][i].first] > L[node] + v[node][i].second){
                L[v[node][i].first]= L[node] + v[node][i].second;
                T.pb(v[node][i].first);
                push_heap(T.begin(),T.end(),cmp);
        }


    }
    }


}

int main(){

    in>>n>>m;

    for(int i=1;i<=m;i++)
    {
        in>>x>>y>>c1;
        v[x].pb({y,c1});


    }
    dijkstra();
    for(int i=2;i<=n;i++){
        if(L[i] == INF)
            L[i]=0;
        out<<L[i]<<" ";

        }








    return 0;
}