#include <bits/stdc++.h>
using namespace std;



ifstream fin ("dijkstra.in");
ofstream fout("dijkstra.out");


vector<vector<pair<int,int>>> g;
int n,m;
const int INF=INT_MAX-1;



void disjkstra(int x) {

    priority_queue<pair<int,int>> pq;
    pq.push({0,x});
    vector<int> pos(n+1,-INF);
    pos[1]=0;

    while(pq.size()){
        auto curr=pq.top();
        pq.pop();
        cout<<curr.second<<"\n";
        for(auto next:g[curr.second]){
            int d=next.first+curr.first;
            if(-d< -pos[next.second]){
                pos[next.second]=d;
                pq.push({d,next.second});
            }
        }
    }

    for(int i=2;i<pos.size();++i){
        fout<<(pos[i]==INF? 0:-pos[i])<<" ";
    }

}



int main() {
    fin>>n>>m;
    g.resize(n+1);
    for(int i=1;i<=m;++i){
        int a,b,c;
        fin>>a>>b>>c;
        g[a].push_back({-c,b});
    }
    disjkstra(1);
}