#include <stdio.h>
#include <stdlib.h>
#include <vector>
#define MAX 250005
#define INF 100000007
using namespace std;

typedef struct{
	int *val, *key;
	int nr;
} Heap;

typedef struct{
	int node, cost;
} Vertex;

void insert(Heap* h, int x, int k, int* v);
void extract(Heap* h, int* v, int** x);
void modkey(Heap* h, int* v, int x, int k);

int main(){
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	int n, m, a[MAX][3], i, *index, *d;
	Heap h;
	scanf("%d%d", &n, &m);
	vector<Vertex>* L = new vector<Vertex>[n + 1];
	h.val = (int*)malloc((2 * n + 3) * sizeof(int));
	if(!h.val) return 0;
	h.key = (int*)malloc((2 * n + 3) * sizeof(int));
	if(!h.key){ free(h.val); return 0;}
	h.nr = -1;
	index = (int*)calloc(n + 1, sizeof(int));
	if(!index){ free(h.val); free(h.key); return 0;}
	d = (int*)malloc((n + 1) * sizeof(int));
	if(!d){ free(h.val); free(h.key); free(index); return 0;}

	for(i = 0; i <= n; i++){
		d[i] = INF;
		h.key[2 * i] = INF;
		h.key[2 * i + 1] = INF;
	}
	h.key[2 * n + 2] = INF;
	for(i = 0; i < m; i++){
		scanf("%d%d%d", &a[i][0], &a[i][1], &a[i][2]);
		if(a[i][0] == 1)
			d[a[i][1]] = a[i][2];
		else{
			Vertex aux;
			aux.node = a[i][1];
			aux.cost = a[i][2];
			L[a[i][0]].push_back(aux);
		}
	}

	for(i = 2; i <= n; i++)
		insert(&h, i, d[i], index);

	for(i = n; i >= 2; i--){
		int *x = NULL;
		extract(&h, index, &x);
		while(!L[x[0]].empty()){
			Vertex aux = L[x[0]].back();
			L[x[0]].pop_back();
			if(d[aux.node] > x[1] + aux.cost){
				d[aux.node] = x[1] + aux.cost;
				modkey(&h, index, aux.node, d[aux.node]);
			}
		}
	}

	for(i = 2; i <= n; i++){
		if(d[i] == INF)
			printf("0 ");
		else
			printf("%d ", d[i]);
	}
	printf("\n");
	return 0;
}

void insert(Heap* h, int x, int k, int* v){
	h->nr++;
	h->val[h->nr] = x;
	h->key[h->nr] = k;
	v[x] = h->nr;

	int i = h->nr, j = (i - 1) / 2, aux;
	while(i > 0 && h->key[j] > h->key[i]){
		aux = h->val[i];
		h->val[i] = h->val[j];
		h->val[j] = aux;
		aux = h->key[i];
		h->key[i] = h->key[j];
		h->key[j] = aux;
		v[h->val[i]] = i;
		v[h->val[j]] = j;
		i = j;
		j = (i - 1) / 2;
	}
}

void extract(Heap* h, int* v, int** x){
	*x = (int*)malloc(2 * sizeof(int));
	if(!(*x)) return;
	(*x)[0] = h->val[0];
	(*x)[1] = h->key[0];
	h->val[0] = h->val[h->nr];
	h->key[0] = h->key[h->nr];
	h->nr--;
	int i = 0, aux, j;
	while(h->key[i] > h->key[2 * i + 1] || h->key[i] > h->key[2 * i + 2]){
		j = h->key[2 * i + 1] > h->key[2 * i + 2] ? 2 * i + 2 : 2 * i + 1;
		aux = h->val[i];
		h->val[i] = h->val[j];
		h->val[j] = aux;
		aux = h->key[i];
		h->key[i] = h->key[j];
		h->key[j] = aux;
		v[h->val[i]] = i;
		v[h->val[j]] = j;
		i = j;
	}
}

void modkey(Heap* h, int* v, int x, int k){
	int i = v[x], j, aux;
	h->key[i] = k;

	if(i > 0){
		j = (i - 1) / 2;
		if(h->key[j] > h->key[i])
			while(i > 0 && h->key[j] > h->key[i]){
				aux = h->val[i];
				h->val[i] = h->val[j];
				h->val[j] = aux;
				aux = h->key[i];
				h->key[i] = h->key[j];
				h->key[j] = aux;
				v[h->val[i]] = i;
				v[h->val[j]] = j;
				i = j;
				j = (i - 1) / 2;
			}
	}
}