#include <fstream>
#include <vector>
#include <set>
#include <bitset>
#define DIM 50011
#define INF 1000111
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m;
int D[DIM];

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

int main(void){
    register int i,j,x,y,c;
    vector<pair<int,int> >::iterator it;
    set<pair<int,int> >::iterator z;
    pair<int,int> p;

    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()){
        z=S.begin();
        p=*z;
        S.erase(S.begin());
        for(it=L[p.second].begin();it!=L[p.second].end();it++){
            if(D[it->second]>it->first+D[p.second]){
                D[it->second]=it->first+D[p.second];
                S.insert(make_pair(D[it->second],it->second));
            }
        }
        viz[p.second]=1;
    }

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