#include <cstdio>
#include <vector>
#define Nmax 50005
#define INF 2000000000

using namespace std;

int N,H[Nmax],d[Nmax],poz[Nmax];

struct coord
{
    int n,cost;
};
vector <coord> L[Nmax];

inline void Swap(int i, int j)
{
    int hi=H[i],hj=H[j];
    H[i]=hj; H[j]=hi;
    poz[hi]=j; poz[hj]=i;
}

inline void DownHeap(int k)
{
    int fiu,gata;
    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 UpHeap(int k)
{
    int tata;
    tata=k/2;
    while(k>1 && d[H[k]]<d[H[tata]])
    {
        Swap(k,tata);
        k=tata; tata=k/2;
    }
}

int main()
{
    int M,x,y,z,i,len,nod,j;
    coord w;
    freopen ("dijkstra.in","r",stdin);
    freopen ("dijkstra.out","w",stdout);
    scanf("%d%d", &N,&M);
    while(M--)
    {
        scanf("%d%d%d", &x,&y,&z);
        w.n=y; w.cost=z;
        L[x].push_back(w);
    }

    for(i=2;i<=N;++i)
    {
        d[i]=INF;
        poz[i]=-1;
    }
    H[++H[0]]=1; poz[1]=1;
    while(H[0])
    {
        nod=H[1]; len=L[nod].size();
        H[1]=H[H[0]--];
        DownHeap(1);
        for(i=0;i<len;++i)
        {
            j=L[nod][i].n;
            if(d[j]>d[nod]+L[nod][i].cost)
            {
                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]);
                }
            }
        }
    }
    for(i=2;i<=N;++i)
        if(d[i]==INF)
            printf("0 ");
        else
            printf("%d ", d[i]);
    printf("\n");
    return 0;
}