#include <fstream>
#include <cstring>
#include <queue>
#include <vector>
#define nmax 50005
#define f "dijkstra.in"
#define g "dijkstra.out"
#define inf 123456789
using namespace std;

vector< pair<int,int> > gf[nmax];
int n, m, d[nmax], viz[nmax];

struct comp{
    bool operator () (const int &a, const int &b){
        return d[a]>d[b];
    }
};


void bellman_ford_cu_coada_prioritara(){
    memset(d, inf, sizeof(d));//initializez vectorul distantelor minime cu val = inf;
    viz[1]=1;//marchez ca vizitat nodul 1;
    d[1]=0;//initalizez punctul de placare (= 1) cu valoare 0;
    priority_queue<int, vector<int>, comp> Q;//declar coada prioritara

    for(Q.push(1);!Q.empty();Q.pop()){//adaug nodul de plecare/si cat timp coada nu e goala
        int nod = Q.top(); // initalizez nodul (=nodul de minimalizare)
        viz[nod]=0;//marchez nodul ca nevitat;
        for(vector< pair<int,int> >:: iterator it=gf[nod].begin(); it!=gf[nod].end(); it++){//pt fiecare vecin al nodului
            int y = it->first;// y = vecin
            int c = it->second;// c = costul deplasarii nod - y;
            if (d[y] > d[nod] + c){// daca pot minimaliza distanta nodului y prin nodul "nod" atunci
                d[y] = d[nod] + c;// distanta nodului y ia acea valoare
                if (viz[y]==0){//daca nu am mai vizitat acest nod
                    Q.push(y);//il introduc in coada
                    viz[y]=1;//si il machez ca vizitat;
                }
            }
        }
    }
}

int main(){

    ifstream in(f);
    ofstream out(g);

    in>>n>>m;
    for(int i=1; i<=m; i++){
        int x, y, c;
        in>>x>>y>>c;
        gf[x].push_back(make_pair(y,c));
    }
    bellman_ford_cu_coada_prioritara();

    for(int i=2; i<=n; i++) out<<(d[i] < inf ? d[i] : 0)<<" ";

    in.close();
    out.close();
    return 0;
}