#include<cstdio>
#include<vector>
#include<deque>
using namespace std;

const int N=50001,INF=2000000001;

int cost[N],n,m;

struct xy{
	int b,c;
};

vector <xy> v[N];

deque <int> q;

void ini()
{
	for( int i=1 ; i<=n ; ++i )
		cost[i]=INF;
}

void read()
{
	int a,b,c;
	xy d;
	scanf("%d%d",&n,&m);
	for( int i=1 ; i<=m ; ++i )
	{
		scanf("%d%d%d",&a,&b,&c);
		d.b=b;
		d.c=c;
		v[a].push_back(d);
	}
}

void check(int x)
{
	for( int i=0 ; i<v[x].size() ; ++i )
		if( cost[x] + v[x][i].c < cost[v[x][i].b] )
		{
			cost[v[x][i].b]=cost[x]+v[x][i].c;
			q.push_back(v[x][i].b);
		}
}

void bf()
{
	int x;
	while(!q.empty())
	{
		x=q.front();
		check(x);
		q.pop_front();
	}
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	read();
	ini();
	q.push_back(1);
	cost[1]=0;
	bf();
	for( int i=2 ; i<=n ; ++i )
		printf("%d ",cost[i]);
	return 0;
}