#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;

ifstream cin("/home/mihai/Documents/c++/A/A.in");
ofstream cout("/home/mihai/Documents/c++/A/A.out");

//ifstream cin("dijkstra.in");
//ofstream cout("dijkstra.out");

#define pb push_back

const int oo = (1 << 30);
const int N = 5e4 + 17;

vector <pair <int, int> > v[N];

int D[N];

bitset <N> viz;

struct cmp
{
	bool operator() (int x, int y)
	{
		return D[x] > D[y];
	}
};

priority_queue <int, vector <int>, cmp> Q;

int n;

void Dijkstra()
{
	for(int i = 2; i <= n; i++)
		D[i] = oo;
	D[0] = 0;
	Q.push(1);
	viz[1] = 1;
	while(!Q.empty())
	{
		int nod = Q.top();
		Q.pop();
		viz[nod] = 0;
		for(int i = 0; i < v[nod].size(); i++)
		{
			int vecin = v[nod][i].first;
			int cost = v[nod][i].second;
			if(D[vecin] > D[nod] + cost)
				{
					D[vecin] = D[nod] + cost;
					if(viz[vecin] == 0)
						viz[vecin] = 1, Q.push(vecin);
				}
		}
	}
}

int main()
{
	int m;
	cin >> n >> m;
	while(m--)
	{
		int x, y, c;
		cin >> x >> y >> c;
		v[x].pb({y, c});
	}
	Dijkstra();
	for(int i = 2; i <= n; i++)
		cout << ((D[i] == oo) ? 0 : D[i]) << ' ';
}