#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int const dMax=50005;
int d[dMax];
int csucsok,elek;
int vegtelen (1<<30);

struct comp{
bool operator()(int x,int y)
{
    return d[x] > d[y];
}
};
vector<pair<int,int> >graf [dMax];
vector<pair<int,int> >::iterator it;
bool jart[dMax]={0};
priority_queue<int,vector<int>,comp> sor;

void kiir()
{
    ofstream out("dijkstra.out");
    for(int i=2;i<=csucsok;i++)
    {

        if(d[i]==vegtelen)
        {
            out<<"0";
        }
        else{
        cout<<d[i]<<" ";
        out<<d[i]<<" ";
    }
    }
    cout<<endl;
}

void beolvas()
{
    ifstream in("dijkstra.in");
    in>>csucsok>>elek;
    int a,b,c;
    while(in>>a>>b>>c)
    {
        //beolvas
        graf[a].push_back(make_pair(b,c));
       // graf[b].push_back(make_pair(a,c));
    }
}
void dijkstra(int csucs)
{
    for(size_t i=1;i<=csucsok;i++) d[i]=vegtelen;

    d[csucs]=0;
    sor.push(csucs);
        jart[csucs]=1;

    while(!sor.empty())
    {
    int aktualiscsucs= sor.top();
    sor.pop();
    jart[aktualiscsucs]=0;
        for(int i=0;i<graf[aktualiscsucs].size();i++)
        {
            int szomszedcsucs=graf[aktualiscsucs][i].first;
            int suly=graf[aktualiscsucs][i].second;

            if(d[aktualiscsucs]+suly<d[szomszedcsucs])
            {

               d[szomszedcsucs]=d[aktualiscsucs]+suly;
               if(jart[szomszedcsucs]==0)
               {
                   jart[szomszedcsucs]=1;
                   sor.push(szomszedcsucs);
               }
            }
        }


    }
}
int main()
{
        beolvas();
        dijkstra(1);
        kiir();

    return 0;
}