#include <stdio.h>
#include <vector>

using namespace std;
struct tip{int vf, cost;};
tip heap[250010];
int size;
bool marcat[50010];
int costuri[50010];
int x, y, z;
int n, m;
vector <tip> v[50010];
void up(int poz)
{
    if(heap[poz].cost<heap[poz/2].cost and poz!=1)
    {
        tip aux;
        aux.cost=heap[poz].cost;
        heap[poz].cost=heap[poz/2].cost;
        heap[poz/2].cost=aux.cost;
        aux.vf=heap[poz].vf;
        heap[poz].vf=heap[poz/2].vf;
        heap[poz/2].vf=aux.vf;
        up(poz/2);
    }
}
void insert(tip x)
{
    heap[size+1].vf=x.vf;
    heap[size+1].cost=x.cost;
    up(size+1);
    size++;
}
void down(int poz)
{
    int l=poz*2, r=poz*2+1, best=poz;
    if(l<=size and heap[l].cost<heap[best].cost)
        best=l;
    if(r<=size and heap[r].cost<heap[best].cost)
        best=r;
    if(best!=poz)
    {
        tip aux;
        aux.vf=heap[best].vf;
        heap[best].vf=heap[poz].vf;
        heap[poz].vf=aux.vf;
        aux.cost=heap[best].cost;
        heap[best].cost=heap[poz].cost;
        heap[poz].cost=aux.cost;
        down(best);
    }
}
void pop()
{
    tip aux;
    aux.vf=heap[1].vf;
    heap[1].vf=heap[size].vf;
    heap[size].vf=aux.vf;
    aux.cost=heap[1].cost;
    heap[1].cost=heap[size].cost;
    heap[size].cost=aux.cost;
    size--;
    down(1);
}
void bfs()
{
    tip ins;
    ins.vf=1;
    ins.cost=0;
    insert(ins);
    while(size)
    {
        tip varf;
        varf.vf=heap[1].vf;
        varf.cost=heap[1].cost;
        pop();
        if(marcat[varf.vf]==true) continue;
        marcat[varf.vf]=true;
        costuri[varf.vf]=varf.cost;
        for(int i=0; i<v[varf.vf].size();i++)
        {
            tip aux;
            aux.vf=v[varf.vf][i].vf;
            aux.cost=v[varf.vf][i].cost+costuri[varf.vf];
            if(marcat[aux.vf]==false)
                insert(aux);
        }
    }
    for(int i=2; i<=n; i++)
        printf("%d ", costuri[i]);
}
int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        tip aux;
        scanf("%d %d %d", &x, &y, &z);
        aux.vf=y;
        aux.cost=z;
        v[x].push_back(aux);
    }
    bfs();
    return 0;
}