#include <iostream>
#include <fstream>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int NMAX = 25e4;
struct spec {
	int n1, n2, c;
}a[NMAX];
int n, m;

void citire() {
	f >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int aux;
		f >> aux;
		a[i].n1 = aux;
		f >> aux;
		a[i].n2 = aux;
		f >> aux;
		a[i].c = aux;
	}
}


int costuri[NMAX];
int queue[NMAX - 1];
int queue_pos=1;
void baga_n_queue(int value) {
	queue[queue_pos] = value;
	queue_pos++;
}
void elimina_prim_queue() {
	for (int i = 0; i < queue_pos-1; i++) {
		queue[i] = queue[i + 1];
	}
	queue_pos--;
}

void Dijkstra() {
	for(int i=0;i<m;i++)
		if (a[i].n1 == queue[0]) {
			baga_n_queue(a[i].n2);
			if (costuri[a[i].n2] == 0 || costuri[a[i].n1] + a[i].c < costuri[a[i].n2]) {
				costuri[a[i].n2] = costuri[a[i].n1] + a[i].c;
			}
		}
	elimina_prim_queue();
	if (queue_pos != 0) {
		Dijkstra();
	}

}
void afisare() {
	cout << "AFISARE COSTURI:";
	for (int i = 1; i <= n; i++)cout << costuri[i] << " ";
	cout << "\nAFISARE QUEUE:";
	for (int i = 0; i < queue_pos; i++)cout << queue[i] << " ";
	cout << "\nAFISARE MUCHII:\n";
	for (int i = 0; i < m; i++) {
		cout << a[i].n1 << " " << a[i].n2 << " " << a[i].c << endl;
	}
}
int main() {
	citire();
	costuri[1] = 0;
	queue[0] = 1;
	Dijkstra();
	afisare();
	for (int i = 2; i <= n; i++) {
		g << costuri[i]<<" ";
	}
}