#include <fstream>
#include <vector>
#include <set>
#define DIM 50010
#define INF 1000000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,D[DIM];
bool viz[DIM+50];

set<pair<int,int> > S;
vector<pair<int,int> > L[DIM];

int main(void){
    register int i,j,x,y,c,val,nod,vec,cost;
    pair<int,int> q;

    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y>>c;
        L[x].push_back(make_pair(c,y));
    }

    for(i=2;i<=n;i++)
        D[i]=INF;

    S.insert(make_pair(0,1));
    while(!S.empty()){
        //alegem minimul curent
        val=S.begin()->first;
        nod=S.begin()->second;
        S.erase(S.begin());
        if(viz[nod])
            continue;
        for(i=0;i<L[nod].size();i++){
            if(D[L[nod][i].second]>D[nod]+L[nod][i].first){
                D[L[nod][i].second]=D[nod]+L[nod][i].first;
                S.insert(make_pair(D[L[nod][i].second],L[nod][i].second));
            }
        }
        viz[nod]=true;
    }

    for(i=2;i<=n;i++){
        if(D[i]==INF)
            g<<"0 ";
        else
            g<<D[i]<<" ";
    }
    return 0;
}