#include <iostream>
#include <fstream>
#include <vector>
#include <set>

using namespace std;

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

const int oo = (1<<31)-1 , NMAX = 50015;


vector < pair < int , int > > graf[NMAX];
set < pair < int , int > > s;
long long D[NMAX] , n , m , a , b , c;

int main()
{
    fin >> n >> m;
    int i;
    for(i=1;i<=m;i++)
    {
        fin >> a >> b >> c;
        if(i<=n)
            D[i] = oo;
        graf[a].push_back({b,c});
    }
    for(i;i<=n;i++)
        D[i] = oo;
    D[1] = 0;
    //pe prima pozitie punem distanta iar pe a 2-a nodul
    s.insert({0,1});
    //nodul de pornire este 1
    while(!s.empty())
    {
        int nodcurent = s.begin()->second;
        s.erase(s.begin());
        for(int i=0;i<graf[nodcurent].size();i++)
        {
            int vecin = graf[nodcurent][i].first;
            int cost = graf[nodcurent][i].second;
            cout << vecin << " " << cost << '\n';
            if(D[nodcurent]+cost<D[vecin])
            {

                s.erase({D[vecin],vecin});
                D[vecin] = D[nodcurent]+cost;
                s.insert({D[vecin],vecin});
            }
        }
    }

    for(i=2;i<=n;i++)
    {
        if(D[i]==oo)
            fout << "0 ";
        else fout << D[i] << " ";
    }
    return 0;
}