#include "iostream"
#include "fstream"
#include "queue"
#include "vector"
#define pr pair<int,int>
const int NMAX = 50002;
const int INF = 2000;
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
struct Compare 
{
	bool operator() (const pr &a,const pr &b) const
	{	
		return a.second < b.second;
	}
};

priority_queue< pr, vector< pr >, Compare> Q;
vector<pr> *Graf;
int nr_nod;
int* dist;

void Read()
{
	int from,to,by,muchii;
	in >> nr_nod >> muchii;
	dist = new int[nr_nod+1];
	Graf = new vector<pr>[nr_nod+1];
	for (int i = 0; i < muchii; ++i)
	{
		in >> from >> to >> by;
		Graf[from].push_back(pr(to,by));
	}	
}
void Dijkstra(int sursa)
{
	int to,by,from;
	for (int i = 1; i < nr_nod+1; ++i)
		dist[i] = INF;
	dist[sursa] = 0;
	Q.push(pr(sursa,dist[sursa]));
	
	while (!Q.empty())
	{
		from = Q.top().first;
		Q.pop();
		for (int i = 0; i < Graf[from].size(); ++i)
		{
			to = Graf[from][i].first;
			by = Graf[from][i].second;
			if (dist[to] > dist[from] + by)
			{
				dist[to] = dist[from] + by;
				Q.push(pr(to,dist[to]));
			}
		}
	}
}
void Print()
{
	for (int i = 2; i < nr_nod+1; ++i)
		if(dist[i] == INF)
			out << "0 ";
		else
			out << dist[i] << " ";
}
int main(int argc, char const *argv[])
{
	Read();
	afis();
	Dijkstra(1);
	//Print();
	return 0;
}