#include <iostream>
#include <vector>
#include <utility>
#include <fstream>

#define NMAX 50001
#define INF 20001
using namespace std;

vector < pair <int,int> > vecini[NMAX];
int vizitat[NMAX];
int distante[NMAX];
vector <int> set;

int alege_minim(int n){
    int minim = INF;
    int nod;
    int ok=1;
    for(int i=1;i<=n;i++){
        ok=1;
        if( set.empty() == 0 )
            for(int j=0;j<=set.size();j++)
                if(set[j]==i)ok=0;

        if(ok == 1){
            if(distante[i]<minim)
                nod = i;
        }
    }
    return nod;
}

int main() {
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");

    int n,m,a,b,c;

    f>>n>>m;

    for(int i=0;i<m;i++){
        f>>a>>b>>c;
        vecini[a].push_back( make_pair(c,b) ) ;
    }
    for(int i=1;i<=n;i++){
        distante[i]=INF;
    }

    cout<<vecini[1][1].second<< "      " <<vecini[1][1].first<<endl;

    //Calculam incepand de la nodul 1;
    distante[1]=0;


    while(set.size()<n){
        int nod = alege_minim(n);
        set.push_back(nod);
        for(int i=0;i<vecini[nod].size();i++){
            if( distante[vecini[nod][i].second]  >  distante[nod]+vecini[nod][i].first  )
                distante[vecini[nod][i].second] = distante[nod]+vecini[nod][i].first;
        }
    }

    for(int i=2;i<=n;i++){
        if(distante[i]==INF)
            g<<0<<" ";
        else
            g<<distante[i]<<"   ";
    }


    return 0;
}