#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

vector<pair<int,int> >v[50001];
int heap[50001],poz[50001],cost[50001],N ;
queue<int>q;

void sift(int nod)
{

    if(2*nod<=N)
    {
        int son=2*nod;
        if(son+1<=N&&cost[heap[son+1]]<cost[heap[son]])son++;
        if(cost[heap[nod]]>cost[heap[son]])
        {   int aux;
        aux= heap[nod];
            heap[nod]=heap[son];
            heap[son]=aux;
            poz[heap[nod]]=nod;
            poz[heap[son]]=son;
            nod=son;
            son=2*nod;
            while(son<=N)
            {
                if(son+1<=N&&cost[heap[son+1]]<cost[heap[son]])son++;
                if(cost[heap[nod]]>cost[heap[son]])
                {int aux;
        aux= heap[nod];
                    heap[nod]=heap[son];
                    heap[son]=aux;
                    poz[heap[nod]]=nod;
                    poz[heap[son]]=son;

                    nod=son;
                    son=2*nod;
                }
                else return;
            }
        }
    }return;
}

void percolate(int k)
{
    int key,nod=heap[k];
    key=k;
    while(key>=2&&cost[nod]<cost[heap[key/2]])
    {
        heap[key]=heap[key/2];
        poz[heap[key/2]]=key;
        key=key/2;
    }
    heap[key]=nod;
    poz[nod]=key;

}


int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int i,n,j,p,m,a,b,c,nod;
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        v[a].push_back(make_pair(b,c));

    }
    for(i=1;i<=n;i++)
    {
         cost[i]=1987654321;
       poz[i]=heap[i]=i;
    }
    cost[1]=0;
    N=n;

    for(j=1; j<=n; j++)
    {int aux=heap[N];
        nod=heap[1];
        heap[1]=heap[N];
        heap[N]=nod;
        poz[nod]=N;

        poz[aux]=1;
        N--;
        sift(1);
        p=v[nod].size();
        for(i=0;i<p;i++)
        {
            if(cost[v[nod][i].first]>cost[nod]+v[nod][i].second)
            {
                cost[v[nod][i].first]=cost[nod]+v[nod][i].second;
                percolate(poz[v[nod][i].first]);

            }
        }

    }


    for(i=2;i<=n;i++)
    {
        if(cost[i]==1987654321)printf("0 ");
        else printf("%d ", cost[i]);
    }

    return 0;
}