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

#define BIN 65537
#define MAX 50001

using namespace std;

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

inline void input()
{
    int M,x,y,c;
    ifstream in;

    in.open("dijkstra.in");

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

    in.close();
}

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

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

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

inline void HeapDown(int nod)
{
    int Down,ind=H[nod],L,R;

    while(1)
    {
        Down=0;
        L=nod<<1;
        R=(nod<<1)+1;

        if(R<BIN&&H[R]) Down=2;
        else
        if(L<BIN&&H[L]) Down=1;

        if(!Down)
        {
            H[nod]=ind;
            pos[ind]=nod;
            return;
        }

        if(Down==2)
        {
            if(D[H[L]]<D[H[R]])
            {
                if(D[H[L]]<D[ind])
                {
                    H[nod]=H[L];
                    pos[H[nod]]=nod;
                    nod=L;
                }
                else
                {
                    H[nod]=ind;
                    pos[ind]=nod;
                    return;
                }
            }
            else
            {
                if(D[H[R]]<D[ind])
                {
                    H[nod]=H[R];
                    pos[H[nod]]=nod;
                    nod=R;
                }
                else
                {
                    H[nod]=ind;
                    pos[ind]=nod;
                    return;
                }
            }
        }
        else
        if(D[H[L]]<D[ind])
        {
            H[nod]=H[L];
            pos[H[nod]]=nod;
            nod=L;
        }
        else
        {
            H[nod]=ind;
            pos[ind]=nod;
            return;
        }
    }
}

inline void Cut()
{
    H[1]=H[cnt];
    pos[H[1]]=1;
    H[cnt]=0;
    cnt--;

    HeapDown(1);
}

inline void dijkstra()
{
    int S,x,c;
    vector <pair<int,int> >::iterator it;

    memset(H,0,sizeof(H));
    memset(pos,0,sizeof(pos));
    memset(D,-1,sizeof(D));
    pos[1]=1;
    H[1]=1;
    D[1]=0;
    cnt=1;

    while(cnt)
    {
        pos[1]=1;
        S=H[1];

        for(it=v[S].begin();it!=v[S].end();++it)
        {
            x=(*it).first;
            c=(*it).second;

            if(D[x]==-1)
            {
                D[x]=D[S]+c;
                H[++cnt]=x;
                HeapUp(cnt);
            }
            else
            if(D[x]>D[S]+c)
            {
                D[x]=D[S]+c;
                HeapUp(pos[x]);
            }
        }

        Cut();
    }
}

inline void output()
{
    ofstream out;

    out.open("dijkstra.out");

    for(int i=2;i<N;i++)
        if(D[i]>0) out<<D[i]<<' ';
        else out<<"0 ";
    if(D[N]>0) out<<D[N]<<'\n';
    else out<<"0\n";

    out.close();
}

int main()
{
    input();
    dijkstra();
    output();

    return 0;
}