#include <iostream>
#include <vector>
#include <fstream>
#include <utility>
#include <set>
#include <iterator>
#include <queue>
#include <algorithm>
#include <queue>
using namespace std;

int s=0,n,m;
vector < pair <int,int> > muchii [50002];
int tati[50002], d[50002], v[50002];

class comp {
    public:
    bool operator () (int a, int b) const {
        return d[a]<d[b];
    }
};

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));
        //muchii[t2].push_back(make_pair(t1,c)); //daca graful e neorientat
    }
}

void djkistra () {
    for (int i=0; i<n; i++) {
        d[i]=1000000000; //=inf
    }
    d[s]=0;
    v[s]=1;
    tati[s]=s;
    priority_queue <int, vector<int>, comp> coada; //nu e chiar coada
    int si=muchii[s].size();
    for (int i=0; i<si; i++) {
        int f=muchii[s][i].first;
        if (v[f]==0) {
            //cout<<"Am inserat muchia ("<<s+1<<","<<f+1<<")"<<endl;
            d[f]=d[s]+muchii[s][i].second;
            tati[f]=s;
            coada.push(f);
        }
    }
    int k=0;
    while (!coada.empty()) {
        int cur=coada.top();
        coada.pop();
        /*cout<<"k: "<<k<<endl;
        cout<<"cur: "<<cur+1<<endl;*/
        int si=muchii[cur].size();
        for (int i=0; i<si; i++) {
            int f=muchii[cur][i].first;
            //cout<<"Am inserat muchia ("<<cur+1<<","<<f+1<<")"<<endl;
            if (d[f]>d[cur]+muchii[cur][i].second) { //relaxarea
                d[f]=d[cur]+muchii[cur][i].second;
                tati[f]=cur;
                if (!v[f]) coada.push(f);
            }
        }
        v[cur]=1;
        k++;
    }
}


int main()
{
    citire();
    /*for (int i=0; i<n; i++) {
        cout<<"Nodul "<<i+1<<": ";
        for (int j=0; j<muchii[i].size(); j++) {
            cout<<"("<<muchii[i][j].first+1<<","<<muchii[i][j].second<<") ";
        }
        cout<<endl;
    }*/
    cout<<endl<<endl;
    djkistra();
    cout<<endl<<endl;
    //cout<<"Sursa: "<<s+1<<endl;

    ofstream fout("dijkstra.out");
    for (int i=1; i<n; i++) {
        if (d[i]==1000000000) {d[i]=0;}
        cout<<"Nodul "<<i+1<<" cu tatal "<<tati[i]+1<<" si distanta "<<d[i]<<endl;
        fout<<d[i]<<" ";
    }
    return 0;
}