#include <bits/stdc++.h>
#define DM 50005
#define pb push_back
#define x first
#define y second
#define pii pair<int,int>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

bitset<DM>viz;
int best[DM],n,m,a,b,c;
priority_queue<pii,vector<pii>,greater<pii> >q;
vector<pii>mc[DM];

int main()
{
    fin>>n>>m;
    for(int i=2;i<=n;++i) best[i]=INT_MAX;
    while(m--){
        fin>>a>>b>>c;
        mc[a].pb({b,c});
    }
    q.push({0,1});
    for(;!q.empty();q.pop()){
        int nod=q.top().y;
        if(viz[nod]) continue;
        viz[nod]=1;
        for(auto i:mc[nod]){
            if(best[i.x]>best[nod]+i.y){
                best[i.x]=best[nod]+i.y;
                if(!viz[i.x])q.push({best[i.x],i.x});
            }
        }
    }
    for(int i=2;i<=n;++i){
        if(best[i]==INT_MAX) fout<<0<<" ";
        else fout<<best[i]<<" ";
    }
    return 0;
}