#include <bits/stdc++.h>
#define dim 50010

using namespace std;

vector<pair<int,int> >a[dim];
set<pair<int,int> > q;

int sol[dim];
int f[dim];
int i,n,m,cost,x,y;
 
int main(){
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;
    for (i=1;i<=m;i++){
        fin>>x>>y>>cost;
        a[x].push_back({y,cost});
    }
    for (i=1;i<=n;i++){
        sol[i]=INT_MAX;
    }
    q.insert({0,1});
    sol[1]=0;
    while (!q.empty()){
        int nod=q.begin()->second;
        f[nod]=1;
        q.erase(q.begin());
        for (auto muchie:a[nod]){
            int vecin=muchie.first;
            int cost=muchie.second;
            if (sol[vecin]>sol[nod]+cost){
                q.erase({sol[vecin],vecin});
                sol[vecin]=sol[nod]+cost;
                q.insert({sol[vecin],vecin});
            }
        }
    }
    for (i=2;i<=n;i++){
        if (sol[i]==INT_MAX) fout<<0<<" ";
        else fout<<sol[i]<<" ";
    }
    return 0;
}