#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair

vector <pair<int,int> > V[50010];
int pr[50010],dist[50010],n,m;
queue <int> Q;
set <pair<int, int> > S;
set <pair<int, int> >::iterator it;
bool u[50010];

void Dijkstra(){
    S.insert(mp(0,1));
    while(S.size()!=0){
        int q;
        it=S.begin();
        q=it->second;
        S.erase(S.begin());
        u[q]=true;
        for (int i=0; i<V[q].size(); i++){
            if (dist[q]+V[q][i].second<dist[V[q][i].first]){
                if (dist[V[q][i].first]!=(1<<30)){
                    S.erase(S.find(mp(dist[V[q][i].first],V[q][i].first)));
                }
                dist[V[q][i].first]=dist[q]+V[q][i].second;
                S.insert(mp(dist[V[q][i].first],V[q][i].first));
            }
        }
    }
}

int main() {
    ifstream cin ("dijkstra.in");
    ofstream cout ("dijkstra.out");
    cin>>n>>m;
    for (int i=1; i<=m; i++){
        int x,y,c;
        cin>>x>>y>>c;
        V[x].pb(mp(y,c));
        //V[y].pb(mp(x,c));
    }
    for (int i=2; i<=n; i++) dist[i]=(1<<30);
    Dijkstra();
    for (int i=2; i<=n; i++) cout<<(dist[i]==(1<<30)?0:dist[i])<<" ";
    return 0;
}