#include <fstream>
#include <vector>
#include <queue>
#define pb push_back
#define mp make_pair
#include<iostream>
using namespace std;
const int MAXN=50002;
const int INF=250002;

typedef pair <int, int> muchie;

typedef vector <muchie> graf;
typedef priority_queue <muchie> coada;

int n,m,D[MAXN];
graf G[MAXN];
coada C;

void dijkstra();

int main () {
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin >> n >> m;
    for (int i = 0 ; i < m ; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].pb(mp(c, y));
    }
    dijkstra();
    for (int i = 2 ; i <= n ; ++i) {
        if (D[i] == INF)
            fout << "0 ";
        else
            fout << D[i] <<' ';
    }
    return 0;
}

void dijkstra(){
    //memset(D,INF,sizeof(D));
    for (int i = 1 ; i <= n ; ++i)
        D[i] = INF;
    D[1] = 0;
    C.push(mp(0, 1));
    while (!C.empty()) {
        muchie E = C.top();
        C.pop();
        int nod = E.second;
        cout<<E.first<<" "<<E.second<<endl;
        for (graf :: iterator it = G[nod].begin() ; it != G[nod].end() ; ++it) {
            if (D[nod] + it -> first < D[it -> second]) {
                D[it -> second] = D[nod] + it -> first;
                C.push(mp(-D[it -> second], it -> second));
            }
        }
    }
}