#include <iostream>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <stack>
#include <algorithm>
#include <set>
#define INF 4000000000
using namespace std;

vector < pair <int,int> > muchii[50002];
int n, m; int v[50002]; unsigned int d[50002];



void citire() {
    ifstream fin("dijkstra.in");
    fin>>n>>m;
    for (int i=0; i<m; i++) {
        int t1, t2, c;
        fin>>t1>>t2>>c;
        t1--; t2--;
        muchii[t1].push_back(make_pair(t2, c));
    }
}

struct sort_set {
    bool operator() (vector <int> a, vector <int> b) const {
        return a[2]<b[2];
    }
};

void dijkstra_heap () {
    for (int i=0; i<n; i++) {d[i]=INF;}
    multiset < vector <int>, sort_set> heap;
    int s=0;
    v[s]=1; d[s]=0;
    for (int i=0; i<muchii[s].size(); i++) {
        vector <int> tmp;
        tmp.push_back(s);
        tmp.push_back(muchii[s][i].first);
        tmp.push_back(muchii[s][i].second);
        heap.insert(tmp);
    }
    int k=1;
    while (!heap.empty()) {
        cout<<k<<endl;
        std::multiset< vector <int>, sort_set>::iterator t=heap.begin();
        vector <int> cur=*t;
        int viz, neviz;
        viz=neviz=0;
        heap.erase(t);
        if (v[cur[0]]==1 && v[cur[1]]==0) {viz=cur[0]; neviz=cur[1];}
        if (d[neviz]>d[viz]+cur[2]) {
            d[neviz]=d[viz]+cur[2];
        }
        if (viz+neviz!=0) {
            k++;
            v[neviz]=1;
            for (int i=0; i<muchii[neviz].size(); i++) {
                int mcur=muchii[neviz][i].first;
                if (!v[mcur]) {
                    vector <int> tmp;
                    tmp.push_back(neviz);
                    tmp.push_back(mcur);
                    tmp.push_back(muchii[neviz][i].second);
                    heap.insert(tmp);
                }
            }
        }
    }

}

int main()
{
    citire();
    dijkstra_heap();
    ofstream fout("dijkstra.out");
    for (int i=1; i<n; i++) {
        cout<<d[i]<<" ";
        fout<<d[i]<<" ";
    }
    return 0;
}