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

using namespace std;

const int maxn=50001;
const int maxm=250001;
const int INF=2000000000;
const int r=1;

struct element
{
    int nod,cost,next;
};

element buff[maxm];
int head[maxn];
int d[maxn];///distante

struct cmp
{
    bool operator ()(int nod1, int nod2)
    {
        return d[nod1] > d[nod2];
    }
};

priority_queue <int,vector<int>,cmp> Heap;

void push(int n1, int n2, int cost, int pos)
{
    buff[pos].nod=n2;
    buff[pos].cost=cost;
    buff[pos].next=head[n1];
    head[n1]=pos;
}

int main()
{
    FILE *f;
    int n,m,a,b,c,i,pos;

    f=fopen("dijkstra.in","r");
    fscanf(f,"%d%d",&n,&m);

    for (i=1; i<=n; i++)
    {
        head[i]=-1;///initializez capetele listelor de adiacenta;
        d[i]=INF;///initializez costurile drumurilor de la nodul r la nodul i
    }
    d[r]=0;///radacina

    pos=1;
    for (i=1; i<=m; i++)///construiesc listele de adiacenta
    {
        fscanf(f,"%d%d%d",&a,&b,&c);
        push(a,b,c,pos);
        pos++;
    }

    fclose(f);

    ///de aici incepe Dijkstra

    Heap.push(r);///pun radacina in heap
    while (!Heap.empty())
    {
        int nc=Heap.top();
        i=head[nc];///extrag din heap primul element

        Heap.pop();
        while (i != -1)
        {
            if (d[nc]+buff[i].cost < d[buff[i].nod])
            {
                d[buff[i].nod]=d[nc]+buff[i].cost;
                Heap.push(buff[i].nod);
            }
            i=buff[i].next;
        }
    }

    ///afisare
    f=fopen("dijkstra.out","w");
    for (i=2; i<=n; i++)
        fprintf(f,"%d ",d[i]);
    fclose(f);
}