#include<cstdio>
#include<queue>
#include<vector>
#define NMAX 50005
#define INF 1<<30
#define vecin first
#define cost second
using namespace std;
int N,M,D[NMAX];
vector<pair<int,int> >V[NMAX];
bool E[NMAX];
struct cmp
{
public:
	bool operator()(int &X,int &Y)
	{ if(D[X] > D[Y]) return 1 ; return 0; }
};
priority_queue<int,vector<int>,cmp >Q;
void citire()
{
	int x,y,c;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i = 0 ; i<=N ; i++)
		D[i] = INF;
	for(int i = 0 ; i<M; i++)
	{
		scanf("%d%d%d",&x,&y,&c);
		V[x].push_back(make_pair(y,c));
	}
}
void DJ()
{
	D[1] = 0;
	Q.push(1);
	E[1] = 1;
	while(Q.size())
	{
		int nod = Q.top();
		E[nod] = 0,Q.pop();
		int i,l = V[nod].size();
		for(i = 0 ; i<l;i++)
		{
			int y = V[nod][i].vecin , c = V[nod][i].cost;
			if(D[y] > (D[nod] + c))
			{
				D[y] = D[nod] + c;
				if(!E[y])
					Q.push(y),E[y] = 1;
			}
		}
	}
}
void afisare()
{
	for(int i = 2 ; i<= N ; i++)
		if(D[i] == INF)
			printf("%d ",0);
		else
			printf("%d ",D[i]);
}
int main()
{
	citire();
	DJ();
	afisare();
	return 0;
}