#include <bits/stdc++.h>

using namespace std;

struct nod
{
   int d;
   int n;
} ad,h[100005];

vector<nod> lst[50005];
int i,j,n,m,a,b,c,rs[50005],dst[50005],loc[50005];

void adh(int x, int nod, int dis)
{
    if (h[x].n==0) {h[x].n=nod; h[x].d=dis; return ;}
    if (h[x].d>dis) {
                       if (h[x*2].d>h[x*2+1].d) adh(x*2+1,h[x].n,h[x].d);
                                           else adh(x*2,h[x].n,h[x].d);
                    }
        else
        {
            if (h[x*2].d>h[x*2+1].d) adh(x*2+1,nod,dis);
                                else adh(x*2,nod,dis);
        }
    return ;
}

void scot(int x)
{
    if (h[x].n==0) return;
    if (h[x*2].d<h[x*2+1].d && h[x*2].n!=0)
    {
        if (h[x*2].n==0) {h[x].n=0; h[x].d=0;} swap(h[x],h[x*2]);
        scot(x*2);
    }
    else
    {
        if (h[x*2+1].n==0)
                           h[x].d=h[x].n=0;
                           else swap(h[x],h[x*2+1]);
        scot(x*2+1);
    }
}

void djk(int x)
{
     for (int j=0;j<lst[x].size();j++)
     {
        i=lst[x][j].n;
        if (dst[i]==-1) {
                         dst[i]=dst[x]+lst[x][j].d;
                         adh(1,i,dst[i]);
                      }
        else
         if (dst[i]<dst[x]+lst[x][i].d) {dst[i]=dst[x]+lst[x][j].d; scot(loc[i]); adh(1,i,dst[i]);}
     }
    scot(1);
    if (h[1].n) djk(h[1].n);
    return;
}

int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>n>>m;
    for (i=2;i<=n;i++) dst[i]=-1;
    for (i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        ad.d=c;
        ad.n=b;
        lst[a].push_back(ad);
    }
    h[1].n=1;
    h[1].d=0;
    djk(1);
    for (i=2;i<=n;i++)
        fout<<dst[i]<<" ";
    return 0;
}