#include "iostream"
#include "fstream"
#include "queue"
#include "vector"
#define pr pair<int,int>
const int NMAX = 50001;
const int INF = 1000;
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[NMAX];
int nr_nod;
int* dist = new int[nr_nod+1];
void read()
{
	int from,to,by,muchii;
	in >> nr_nod >> muchii;
	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 = 0; i < nr_nod; ++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;
			//cout << from << " " << to << " " << by << "\n";
			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)
	{
		out << dist[i] << " ";
	}
}
int main(int argc, char const *argv[])
{
	read();
	Dijkstra(1);
	print();
	return 0;
}