using namespace std;
#include<stdio.h>
#include<vector>
#include<queue>
const int NMAX=50001;
struct nod{
	int t, c;
}un;
vector <nod> a[NMAX] ;
bool inq[NMAX];
queue <int> q;
int n,m,d[NMAX];

void citire()
{
	int x;
	scanf("%d%d", &n,&m);
	for(int i=1;i<=m;++i)
	{	
		scanf("%d%d%d",&x,&un.t,&un.c);
		a[x].push_back(un);
	}
	for(int i=2;i<=n;++i)
		d[i]=1<<30;
}

void rez()
{
	int x=1,y;
	q.push(x);
	inq[x]=true;
	while(!q.empty())
	{	
		x=q.front();
		q.pop();
		inq[x] = false;
		for(int i=0;i<a[x].size();++i)
		{	
			y=a[x][i].t;
			if(d[x]+a[x][i].c<d[y])
			{	
				d[y]=d[x]+a[x][i].c;
				if(!inq[y])
					q.push(y);
			}
		}
	}
	for(int i=2;i<=n;++i)
	printf("%d ", d[i]);
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out", "w",stdout);
	citire();
	rez();
	return 0;
}