#include <fstream>
#include <algorithm>
#include <vector>
#define INF 2000000000

using namespace std;

int N,d[50005],h[50005],poz[50005];
bool viz[50005];

struct Arc
{
    int y,cost;
};
vector <Arc> L[50005];

inline void Read()
{
    Arc w;
    int i,M,x;
    ifstream fin("dijkstra.in");
    fin>>N>>M;
    for(i=1;i<=M;++i)
    {
        fin>>x>>w.y>>w.cost;
        L[x].push_back(w);
    }
    fin.close();
}

inline void Swap(int i, int j)
{
    int aux,c1,c2;
    c1=h[i]; c2=h[j];
    aux=h[i]; h[i]=h[j]; h[j]=aux;
    poz[c1]=j; poz[c2]=i;
}

inline void UpHeap(int k)
{
    int tata=k/2;
    while(k>1 && d[h[k]]<d[h[tata]])
    {
        Swap(tata,k);
        k=tata; tata=k/2;
    }
}

inline void DownHeap(int k)
{
    int fiu=2*k, gata=0;
    while(k<=h[0]/2 && !gata)
    {
        if(fiu+1<=h[0] && d[h[fiu+1]]<d[h[fiu]])
            ++fiu;
        if(d[h[k]]<=d[h[fiu]])
            gata=1;
        else
        {
            Swap(k,fiu);
            k=fiu; fiu=2*k;
        }
    }
}

inline void Dijkstra()
{
    int pas,i,nod,j,len,minim;
    for(i=2;i<=N;++i)
    {
        d[i]=INF;
        poz[i]=-1;
    }

    h[++h[0]]=1; poz[1]=1;
    d[1]=0;
    while(h[0]>0)
    {
        nod=h[1];
        Swap(1,h[0]); --h[0];
        DownHeap(1);

        len=L[nod].size();
        for(i=0;i<len;i++)
        {
            j=L[nod][i].y;
            if(d[nod]+L[nod][i].cost< d[j])
            {
                d[j]=d[nod]+L[nod][i].cost;
                if(poz[j]!=-1)
                    UpHeap(poz[j]);
                else
                {
                    h[++h[0]]=j;
                    poz[j]=h[0];
                    UpHeap(h[0]);
                }
            }
        }
    }
    ofstream fout("dijkstra.out");
    for(i=2;i<=N;i++)
        if(d[i]==INF)
            fout<<0<<" ";
        else
            fout<<d[i]<<" ";
    fout<<"\n";
    fout.close();
}

int main()
{
    Read();
    Dijkstra();
    return 0;
}