//
// main.cpp
// Traktor
//
// Created by Jędrzej Dudzicz on 23.04.2017.
// Copyright © 2017 Jędrzej Dudzicz. All rights reserved.
//
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
using namespace std;
bool odwiedzone[200006];
int odleglosc[200006];
int wypisz[200006];
priority_queue<pair<int,int> >kolejka;
vector<pair<int,int> > tablica[200006];
int k=0;
void dfs(int v){
wypisz[k]=v;
k++;
for(int i=0;i<tablica[v].size();++i){
int t1 = tablica[v][i].first;//odleglosc
int t2 = tablica[v][i].second;//sasiad
if(odwiedzone[t2]==0&&odleglosc[v]==(odleglosc[t2]+t1)){
odwiedzone[t2]=1;
dfs(t2);
}
}
}
void Dikstra(){
for(int i=1;i<=200005;++i)odleglosc[i]=1000000005;
int wierzcholki,krawedzie,a,b,waga,index;
scanf("%d%d",&wierzcholki,&krawedzie);
for(int i=0;i<krawedzie;++i){
scanf("%d%d%d",&a,&b,&waga);
tablica[a].push_back(make_pair(waga,b));
tablica[b].push_back(make_pair(waga,a));
}
odleglosc[1]=0;
kolejka.push(make_pair(0,1));
while(!kolejka.empty()){
index=kolejka.top().second;
kolejka.pop();
if(odwiedzone[index]==0){
odwiedzone[index]=1;
for(int i=0;i<tablica[index].size();++i){
int t1 = tablica[index][i].first;
int t2 = tablica[index][i].second;
if(odleglosc[t2]>odleglosc[index]+t1){
odleglosc[t2]=odleglosc[index]+t1;
kolejka.push(make_pair((-t1),t2));
}
}
}
}
for(int i=1;i<=200005;++i)odwiedzone[i]=0;
odwiedzone[wierzcholki]=1;
dfs(wierzcholki);
sort(wypisz,wypisz+k);
for(int i=0;i<k;++i){
printf("%d\n",wypisz[i]);
}
for(int i=1;i<=wierzcholki;++i){
printf("%d ",odleglosc[i]);
}
}
int main(){
Dikstra();
return 0;
}
Ly8KLy8gIG1haW4uY3BwCi8vICBUcmFrdG9yCi8vCi8vICBDcmVhdGVkIGJ5IErEmWRyemVqIER1ZHppY3ogb24gMjMuMDQuMjAxNy4KLy8gIENvcHlyaWdodCDCqSAyMDE3IErEmWRyemVqIER1ZHppY3ouIEFsbCByaWdodHMgcmVzZXJ2ZWQuCi8vCgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxjc3RkaW8+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxjbWF0aD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKYm9vbCBvZHdpZWR6b25lWzIwMDAwNl07CmludCBvZGxlZ2xvc2NbMjAwMDA2XTsKaW50IHd5cGlzelsyMDAwMDZdOwpwcmlvcml0eV9xdWV1ZTxwYWlyPGludCxpbnQ+ID5rb2xlamthOwp2ZWN0b3I8cGFpcjxpbnQsaW50PiA+IHRhYmxpY2FbMjAwMDA2XTsKCmludCBrPTA7CnZvaWQgZGZzKGludCB2KXsKICAgIHd5cGlzeltrXT12OwogICAgaysrOwogICAgZm9yKGludCBpPTA7aTx0YWJsaWNhW3ZdLnNpemUoKTsrK2kpewogICAgICAgIGludCB0MSA9IHRhYmxpY2Fbdl1baV0uZmlyc3Q7Ly9vZGxlZ2xvc2MKICAgICAgICBpbnQgdDIgPSB0YWJsaWNhW3ZdW2ldLnNlY29uZDsvL3Nhc2lhZAogICAgICAgIGlmKG9kd2llZHpvbmVbdDJdPT0wJiZvZGxlZ2xvc2Nbdl09PShvZGxlZ2xvc2NbdDJdK3QxKSl7CiAgICAgICAgICAgIG9kd2llZHpvbmVbdDJdPTE7CiAgICAgICAgICAgIGRmcyh0Mik7CiAgICAgICAgfQogICAgfQp9CnZvaWQgRGlrc3RyYSgpewogICAgZm9yKGludCBpPTE7aTw9MjAwMDA1OysraSlvZGxlZ2xvc2NbaV09MTAwMDAwMDAwNTsKICAgIGludCB3aWVyemNob2xraSxrcmF3ZWR6aWUsYSxiLHdhZ2EsaW5kZXg7CiAgICBzY2FuZigiJWQlZCIsJndpZXJ6Y2hvbGtpLCZrcmF3ZWR6aWUpOwogICAgCiAgICBmb3IoaW50IGk9MDtpPGtyYXdlZHppZTsrK2kpewogICAgICAgIHNjYW5mKCIlZCVkJWQiLCZhLCZiLCZ3YWdhKTsKICAgICAgICB0YWJsaWNhW2FdLnB1c2hfYmFjayhtYWtlX3BhaXIod2FnYSxiKSk7CiAgICAgICAgdGFibGljYVtiXS5wdXNoX2JhY2sobWFrZV9wYWlyKHdhZ2EsYSkpOwogICAgICAgIAogICAgfQogICAgb2RsZWdsb3NjWzFdPTA7CiAgICBrb2xlamthLnB1c2gobWFrZV9wYWlyKDAsMSkpOwogICAgd2hpbGUoIWtvbGVqa2EuZW1wdHkoKSl7CiAgICAgICAgaW5kZXg9a29sZWprYS50b3AoKS5zZWNvbmQ7CiAgICAgICAga29sZWprYS5wb3AoKTsKICAgICAgICBpZihvZHdpZWR6b25lW2luZGV4XT09MCl7CiAgICAgICAgICAgIG9kd2llZHpvbmVbaW5kZXhdPTE7CiAgICAgICAgICAgIGZvcihpbnQgaT0wO2k8dGFibGljYVtpbmRleF0uc2l6ZSgpOysraSl7CiAgICAgICAgICAgICAgICBpbnQgdDEgPSB0YWJsaWNhW2luZGV4XVtpXS5maXJzdDsKICAgICAgICAgICAgICAgIGludCB0MiA9IHRhYmxpY2FbaW5kZXhdW2ldLnNlY29uZDsKICAgICAgICAgICAgICAgIGlmKG9kbGVnbG9zY1t0Ml0+b2RsZWdsb3NjW2luZGV4XSt0MSl7CiAgICAgICAgICAgICAgICAgICAgb2RsZWdsb3NjW3QyXT1vZGxlZ2xvc2NbaW5kZXhdK3QxOwogICAgICAgICAgICAgICAgICAgIGtvbGVqa2EucHVzaChtYWtlX3BhaXIoKC10MSksdDIpKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIGZvcihpbnQgaT0xO2k8PTIwMDAwNTsrK2kpb2R3aWVkem9uZVtpXT0wOwogICAgb2R3aWVkem9uZVt3aWVyemNob2xraV09MTsKCiAgICBkZnMod2llcnpjaG9sa2kpOwogICAgc29ydCh3eXBpc3osd3lwaXN6K2spOwogICAgZm9yKGludCBpPTA7aTxrOysraSl7CiAgICAgICAgcHJpbnRmKCIlZFxuIix3eXBpc3pbaV0pOwogICAgfQogICAgZm9yKGludCBpPTE7aTw9d2llcnpjaG9sa2k7KytpKXsKICAgICAgICBwcmludGYoIiVkICIsb2RsZWdsb3NjW2ldKTsKICAgIH0KfQppbnQgbWFpbigpewogICAgRGlrc3RyYSgpOwogICAgcmV0dXJuIDA7Cn0KCgo=