#include <stdio.h>
#include <vector>

#define MAXN 50000
#define MAXNPOW2 65536
#define INFINIT 1000000001

using namespace std;

FILE *fin, *fout;

struct muchie{
	int nod, cost;
};

struct nod{
    int cost, viz;
};

vector<muchie> lista[MAXN];
nod noduri[MAXN+1];///santinela pentru aint
int ans[MAXN];

int n, m, npow2;

int my_min(int a, int b){
    return a<b?a:b;
}

struct fen{
    int v[MAXNPOW2*2+1];
    void build(){
        int i;
        for(i=npow2+n;i<=npow2*2;i++){
            v[i]=n;
        }
        for(i=npow2-1;i>=1;i--){
            if(noduri[v[i*2]].cost<noduri[v[i*2+1]].cost){
                v[i]=v[i*2];
            }
            else{
                v[i]=v[i*2+1];
            }
        }
    }
    void update(int pos){
        pos+=npow2;
        for(pos/=2;pos;pos>>=1){
            if(noduri[v[pos*2]].cost<noduri[v[pos*2+1]].cost){
                v[pos]=v[pos*2];
            }
            else{
                v[pos]=v[pos*2+1];
            }
        }
    }
};

fen aint_min;

void dijkstra(int poz){
	int cn;
	unsigned int i;
    cn=n-1;
    while(cn--){
        for(i=0;i<lista[poz].size();i++){
			if(!noduri[lista[poz][i].nod].viz){
				if(noduri[poz].cost+lista[poz][i].cost<noduri[lista[poz][i].nod].cost){
					noduri[lista[poz][i].nod].cost=noduri[poz].cost+lista[poz][i].cost;
                    aint_min.update(lista[poz][i].nod);
				}
			}
        }
        ans[poz]=noduri[poz].cost;
        noduri[poz].cost=INFINIT;
		noduri[poz].viz=1;
		aint_min.update(poz);
        poz=aint_min.v[1];
    }
    ans[poz]=noduri[poz].cost;
}

void build_nodes(int poz){
    int i;
    noduri[poz].cost=0;
    noduri[n].cost=INFINIT;///santinela
    for(i=0;i<n;i++){
        if(i!=poz){
            noduri[i].cost=INFINIT;
        }
        aint_min.v[npow2+i]=i;
    }
}

void read_and_build_graph(){
	muchie aux;
	int i, n1, n2, cost;
	fin=fopen("dijkstra.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    npow2=1<<(32-__builtin_clz(n-1));
    for(i=0;i<m;i++){
        fscanf(fin, "%d%d%d", &n1, &n2, &cost);
        n1--;
        n2--;
        aux.nod=n2;
        aux.cost=cost;
        lista[n1].push_back(aux);
    }
    fclose(fin);
}

void write_ans(){
    int i;
    fout=fopen("dijkstra.out", "w");
    for(i=1;i<n;i++){
        fprintf(fout, "%d ", ans[i]);
    }
    fclose(fout);
}

int main()
{
	read_and_build_graph();
	build_nodes(0);
	dijkstra(0);
	write_ans();
    return 0;
}