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



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

const int INF=INT_MAX-1;

int n,m;
vector<vector<pair<int,int>>> g;


void disjkstra(){

    static vector<int> dist(n+1,INF);
    dist[1]=0;
    struct cmp{
        bool operator() (int a,int b){
            return dist[a]>dist[b];
        };
    };
    priority_queue<int, vector<int>, cmp> pq;
    pq.push(1);
    vector<bool> viz(n+1,0);

    while(pq.size()){
        int nd=pq.top();
        pq.pop();

        cout<<nd<<"\n";

        for(auto it:g[nd]){
            int nnd=it.second, d=it.first+dist[nd];
            cout<<nnd<<" - ";
            dist[nnd]=min(d,dist[nnd]);
            if(!viz[nnd])
                pq.push(nnd), viz[nnd]=1;
        }
    }
    for(int i=2;i<dist.size();++i)
        fout<<dist[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();
}