#include <iostream>
#include <vector>
#include <set>
#define MP make_pair

using namespace std;

const int INF = int(2e9);
vector<pair<int,int> > G[50001];
int n , m , d[50001] ;

void dijkstra()
{
	set<pair<int,int> > s;
	for(int i=2;i<=n;++i) d[i]=INF;
	s.insert(MP(0,1));
	while(s.empty()==false)
	{
		int cost = (*s.begin()).first , nod = (*s.begin()).second;
		s.erase(*s.begin());
		for(int i=0;i<G[nod].size();++i)
			if(d[G[nod][i].second]==INF || d[G[nod][i].second]> cost + G[nod][i].first)
				d[G[nod][i].second] =  cost + G[nod][i].first, s.insert(MP(d[G[nod][i].second],G[nod][i].second));
	}

}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i=1 , a , b , c;i<=n;++i)
		scanf("%d %d %d",&a,&b,&c) , G[a].push_back(MP(c,b));

	dijkstra();

	for(int i=2;i<=n;++i)
		printf("%d ",d[i]==INF ? 0 : d[i]);

	return 0;
}