#include <fstream>
#include <bitset>
#include <algorithm>
using namespace std;
const int inf = 1 << 30;
struct node{
    int  info, cost;
    node* next;
};
int H[50001], d[50001], N, M, a, b, c, P[50001], cnt = 0;
bitset<50001> v;
node* No[50001];
ifstream f("dijkstra.in");
ofstream of("dijkstra.out");
void per(int k){
	if (k > 1){
		int f = k >> 1;
		if (d[H[f]] > d[H[k]]){
			swap(H[k], H[f]);
			swap(P[H[k]], P[H[f]]);
			per(f);
		}
	}
}
void sift(int poz)
{
	int f;
	if (poz <= cnt / 2){
		if (poz * 2 + 1 <= cnt)
		if (d[H[poz * 2]] < d[H[poz * 2 + 1]])
			f = 2 * poz;
		else f = 2 * poz + 1;
		else f = 2 * poz;
		if (d[H[poz]]>d[H[f]]){
			swap(H[poz], H[f]);
			swap(P[H[poz]], P[H[f]]);
			sift(f);
		}
	}
}
void add(int x){
    H[++cnt] = x;
    P[x] = cnt;
    per(cnt);
}
int rad(){
    int x = H[1];
    swap(H[1], H[cnt]);
    P[H[1]] = 1;
    --cnt;
    sift(1);
    return x;
}
int main(){
    f >> N >> M;
    d[1] = 0;
    for (int i = 2; i <= N; ++i)
        d[i] = inf;
    for (int i = 1; i <= M; ++i){
        f >> a >> b >> c;
        node* p=new node();
        p->info = b;
        p->cost = c;
        p->next = No[a];
        No[a] = p;
    }
    add(1);
    v[1] = 1;
    while (cnt){
        int x = rad();
        for (node*p = No[x]; p != 0;p=p->next)
        if (!v[p->info] || d[p->info] > d[x] + p->cost){
            v[p->info] = 1;
            d[p->info] = d[x] + p->cost;
            if (!P[p->info])add(p->info);
            else per(P[p->info]);
        }
    }
    for (int i =2; i <= N;++i)
    if (d[i] == inf)of << 0 << " ";
    else of << d[i] << " ";
    }