//
//  main.cpp
//  dijkstra
//
//  Created by Catalina Brinza on 12/17/13.
//  Copyright (c) 2013 Catalina Brinza. All rights reserved.
//

#include <fstream>
#include <vector>
#define nr 50001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct strut
{
    int a,b;
};
vector <strut > vec[nr]; // lista cu noduri
vector <strut> h; //heap


int main()
{int n,m,i,j,y,x,z;
    int broasca[nr];
    strut aux;
    aux.a=0;
    aux.b=0;
    f>>n>>m;
    for (i=1;i<=n;++i) broasca[i]=-1;
    h.push_back(aux);

    for (i=1;i<=m;++i)
    {
        f>>x>>y>>z;
        strut q;
        q.a=y;
        q.b=z;
        vec[x].push_back(q);
        if (x==1)
        {
            broasca[y]=z;
            h.push_back(q);
            int in=i;
            while (h[in].b<h[in/2].b)
            {
                aux=h[in];
                h[in]=h[in/2];
                h[in/2]=aux;
                in=in/2;
            }
        }
    }
    m=n;
    n=h.size();
    while (n!=0)
    {
        x=h[1].a; // heapuire
        i=0;
        while (vec[x].size()!=i)
        {
            if (broasca[vec[x][i].a]==-1)
            {
                broasca[vec[x][i].a]=vec[x][i].b+broasca[x];
                h.push_back(vec[x][i]);
                int in=h.size()-1;
                while (h[in].b<h[in/2].b && in>3)
                {
                    aux=h[in];
                    h[in]=h[in/2];
                    h[in/2]=aux;
                    in=in/2;
                }
      
            }
            else if (broasca[vec[x][i].a]>vec[x][i].b+broasca[x])
                broasca[vec[x][i].a]=vec[x][i].b+broasca[x];
            ++i;
        }
   
        
        if (h.size()>2){
            if (h[1].a!=x)
            {
                if (h[2].a==x) {h[2]=h[h.size()-1]; j=2;}
                else {h[3]=h[h.size()-1];j=3;}
            }
            else {h[1]=h[h.size()-1]; // decapitare+echilibrare heap
                j=1;}
            h.pop_back();
            n=h.size();
        if (j*2+1<=n)
            while (j*2+1<=n)
            {
                if (h[j].b>h[j*2].b && h[j*2].b<h[j*2+1].b)
                {
                    aux=h[j];
                    h[j]=h[j*2];
                    h[j*2]=aux;
                    j=j*2;
                    
                }
                else if ((h[j].b > h[j*2+1].b) && (h[j*2+1].b <= h[j*2].b))
                {
                    aux=h[j];
                    h[j]=h[j*2+1];
                    h[j*2+1]=aux;
                    j=j*2+1;
                }
                else break;
                if (j==n) break;
            }
        else if (j*2==n && h[j].b>h[j*2].b)
        {
            aux=h[j];
            h[j]=h[j*2];
            h[j*2]=aux;
            
        }}
        else break;
    }
    for (i=2;i<=m;++i)
       if (broasca[i]==-1) g<<0<<' '; else
           g<<broasca[i]<<' ';
    f.close();
    g.close();
    
    return 0;
}