#include <fstream>
#include <cstring>
#include <vector>

#define MAX 50001
#define BIN 65537

using namespace std;

vector <pair<int,int> > v[MAX];
int D[MAX],H[BIN],pos[MAX],cnt=0,use[MAX];

inline void HeapUp(int nod)
{
    int ind=H[nod];

    while(nod>1&&D[ind]<D[H[nod>>1]])
    {
        H[nod]=H[nod>>1];
        pos[H[nod]]=nod;
        nod>>=1;
    }

    H[nod]=ind;
    pos[ind]=nod;
}



inline void HeapDown(int nod)
{
    int Down=0,x,y,ind=H[nod];

    x=nod<<1;
    y=(nod<<1)+1;

    if(y<BIN&&H[y]) Down=2;
    else
    if(x<BIN&&H[x]) Down=1;

    while(Down)
    {
        if(Down==2)
        {
            if(D[H[x]]<D[H[y]])
            {
                if(D[ind]>D[H[x]])
                {
                    H[nod]=H[x];
                    pos[H[nod]]=nod;
                    nod=x;
                }
                else
                {
                    H[nod]=ind;
                    pos[ind]=nod;
                    return;
                }
            }
            else
            {
                if(D[ind]>D[H[y]])
                {
                    H[nod]=H[y];
                    pos[H[nod]]=nod;
                    nod=y;
                }
                else
                {
                    H[nod]=ind;
                    pos[ind]=nod;
                    return;
                }
            }
        }
        else
        if(Down==1)
        {
            if(D[ind]>D[H[x]])
            {
                H[nod]=H[x];
                pos[H[nod]]=nod;
                nod=x;
            }
            else
            {
                H[nod]=ind;
                pos[ind]=nod;
                return;
            }
        }
        else
        {
            H[nod]=ind;
            pos[ind]=nod;
            return;
        }

        Down=0;
        x=nod<<1;
        y=(nod<<1)+1;

        if(y<BIN&&H[y]) Down=2;
        else
        if(x<BIN&&H[x]) Down=1;
    }

    H[nod]=ind;
    pos[ind]=nod;
}

inline void Cut(int K)
{
    pos[H[cnt]]=pos[H[K]];
    H[K]=H[cnt];
    H[cnt]=0;

    if(K!=cnt)
    {
        if(K>1&&D[H[K]]<D[H[K>>1]]) HeapUp(K);
        else HeapDown(K);
    }

    cnt--;
}

inline void dij(int nod)
{
    vector <pair<int,int> >::iterator it;

    for(it=v[nod].begin();it!=v[nod].end();it++)
        if(D[(*it).first]<0||D[(*it).first]>D[nod]+(*it).second)
        {
            D[(*it).first]=D[nod]+(*it).second;
            if(D[(*it).first]>=0)
            {
                H[pos[(*it).first]]=(*it).first;
                HeapUp(pos[(*it).first]);
            }
            else
            {
                H[++cnt]=(*it).first;
                pos[(*it).first]=cnt;
                HeapUp(cnt);
            }
        }
}

int main()
{
    int M,N,x,y,c,S;

    ifstream in;
    ofstream out;

    in.open("dijkstra.in");

    in>>N>>M;

    for(;M;M--)
    {
        in>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }

    in.close();

    memset(D,-1,sizeof(D));
    D[1]=0;
    S=1;
    while(1)
    {
        dij(S);
        S=H[1];
        if(use[S]||!S) break;
        else use[S]=1;
        Cut(1);
    }

    out.open("dijkstra.out");

    for(int i=2;i<N;i++)
        out<<D[i]<<' ';
    out<<D[N]<<'\n';

    out.close();

    return 0;
}