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

#define MAX_VAL 1001

typedef struct
{
	int dest, cost;
} con;

istream& operator >> (istream& i, vector<vector<con> >& g)
{
	int N, M;
	i >> N >> M;
	g.resize(N);
	int a1, a2, a3; con* a;
	for (int j = 0; j < M; j++)
	{
		i >> a1 >> a2 >> a3;
		a = new con;
		a->dest = a2 - 1;
		a->cost = a3;
		g[a1 - 1].push_back(*a);
		delete a;
	}
	return i;
}

ostream& operator << (ostream& o, vector<vector<con> >& g)
{
	int i, j;
	for (i = 0; i < g.size(); i++)
	{
		for (j = 0; j < g[i].size(); j++) o << i + 1 << " --" << g[i][j].cost << "--> " << g[i][j].dest + 1 << '\n';
	}
	return o;
}

ostream& operator << (ostream& o, const vector<int>& v)
{
	for (int i = 1; i < v.size(); i++) o << v[i] << ' ';
	o << '\n';
	return o;
}

int main()
{
	vector<vector<con> > graph;
	vector<int> distTo;
	vector<bool> viz;
	ifstream fin("dijkstra.in");
	fin >> graph;
	fin.close();
	distTo.resize(graph.size(), MAX_VAL);
	viz.resize(graph.size(), false);
	distTo[0] = 0;
	queue<int> q;
	q.push(0);
	int i, e;
	while (!q.empty())
	{
		e = q.front();
		//cout << "ELEMENT: " << e + 1 << "\n--------------------------------------------------------------------------------\n";
		for (i = 0; i < graph[e].size(); i++)
		{
			//cout << "Am gasit " << graph[e][i].dest + 1 << "!\n";
			if (distTo[graph[e][i].dest] == MAX_VAL || distTo[graph[e][i].dest] > distTo[e] + graph[e][i].cost)
			{
				//cout << "SCHIMB!\nCostul total precedent: " << distTo[graph[e][i].dest] << "\nCostul total NOU: " << distTo[e] + graph[e][i].cost << '\n';
				distTo[graph[e][i].dest] = distTo[e] + graph[e][i].cost;
				q.push(graph[e][i].dest);
			}
			//else cout << "PASTREZ!\nCostul total precedent: " << distTo[graph[e][i].dest] << "\nCostul total NOU: " << distTo[e] + graph[e][i].cost << '\n';
			//if(!viz[graph[e][i].dest]) q.push(graph[e][i].dest);
			//viz[graph[e][i].dest] = true;
		}
		//cout << "--------------------------------------------------------------------------------\n\n";
		q.pop();
	}
	for (i = 0; i < distTo.size(); i++)
		if (distTo[i] == MAX_VAL)
			distTo[i] = 0;
	ofstream fout("dijkstra.out");
	fout << distTo;
	fout.close();
	return 0;
}