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

#define X1 50001
#define X2 65537
#define INF 0x7fffffff

using namespace std;

ifstream in;
ofstream out;

vector <pair<int,int> > v[X1];

int pos[X1],H[X2],D[X1];

inline void up(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[H[nod]]=nod;
}

inline void down(int nod)
{
    int L,R,son=0,ind;

    L=nod<<1;
    R=(nod<<1)+1;

    if(L<H[0]) son++;
    if(R<H[0]) son++;

    if(son==0) return;
    else
    if(son==1) ind=L;
    else
    if(D[H[L]]>D[H[R]]) ind=R;
    else ind=L;

    if(D[H[ind]]<D[H[nod]])
    {
        son=H[ind];
        H[ind]=H[nod];
        H[nod]=son;
        pos[H[nod]]=nod;
        pos[H[ind]]=ind;
        down(ind);
    }
}

inline void cut()
{
    pos[H[1]]=0;
    H[1]=H[H[0]];
    pos[H[1]]=1;
    H[H[0]]=0;
    H[0]--;
    down(1);
}

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

    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,0,sizeof(D));
    memset(H,0,sizeof(H));
    memset(pos,0,sizeof(pos));
    for(int i=1;i<=N;++i) D[i]=INF;
    D[1]=0;
    H[0]=1;
    H[1]=1;
    pos[1]=1;

    while(H[0])
    {
        nod=H[1];
        cut();
        for(vector <pair<int,int> >::iterator it=v[nod].begin();it!=v[nod].end();++it)
            if(D[(*it).first]>D[nod]+(*it).second)
            {
                D[(*it).first]=D[nod]+(*it).second;
                if(!pos[(*it).first])
                {
                    H[++H[0]]=(*it).first;
                    pos[(*it).first]=H[0];
                }
                up(pos[(*it).first]);
            }
    }

    out.open("dijkstra.out");
    for(int i=2;i<N;++i)
        out<<D[i]<<' ';
    out<<D[N]<<'\n';
    out.close();

    return 0;
}