#include <iostream>
#include <list>
#include <queue>
using namespace std;
list<int*> a[100000];
queue<list<int*>*> q;
int vcost[100000];
int n,m;
void afiseaza(){
	for(int i=2;i<=n;i++){
		printf("%d ",vcost[i]);
	}
	cout<<endl;
}
int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	int nod1,nod2,cost,ok=0;
	int* x;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		x=(int*)malloc(16);
		list<int*> l;
		scanf("%d %d %d",&nod1,&nod2,&cost);
		//cin>>nod1>>nod2>>cost;
		if(a[nod1].size()!=0)l=a[nod1];
		x[0]=nod2,x[1]=cost,x[2]=nod1,x[3]=0;
		l.push_back(x);
		a[nod1]=l;
		//cout<<nod1<<" "<<nod2<<" "<<cost<<endl;
		//cout<<((int*)*next(a[nod1]->begin(),1))[0];		
	}
	q.push(&a[1]);
	while(q.size()!=0){
		list<int*> *l=q.front();
		q.pop();
		for(list<int*>::iterator it=l->begin();it!=l->end();){
			int c=vcost[(*it)[2]]+(*it)[1];
			int c1=vcost[(*it)[0]];
			if(c1==0||c<c1)vcost[(*it)[0]]=c;
			q.push(&a[(*it)[0]]);
			cout<<(*it)[2]<<endl;
			l->erase(it++);
			
			afiseaza();
		}
		
	}

}