#include <stdio.h>
#include <stdlib.h>
#define MAX 2147483647
typedef struct _Node
{
    int nod,length;
    struct _Node *next;
}Node;
Node *p[100001];
void adaugare_dupa(Node *p, int valoare, int length)
{
    Node *q=(Node*)malloc(sizeof(Node));
    q->next=p->next;
    q->nod=valoare;
    q->length=length;
    p->next=q;
}

void show(Node *p, FILE *g)
{
    Node *q=p->next;
    if(q==p)
        fprintf(g,"0\n");
        else
        {
            while(q!=p)
            {
                fprintf(g,"(%d : %d) ", q->nod, q->length);
                q=q->next;
            }
        fprintf(g,"\n");
        }
}
/*void edges_to_matrix()
{
    FILE *f=fopen("grafuri.in", "r");
    FILE *g=fopen("grafuri.out", "w");
    int n,m,M[6][6],x,y,i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            M[i][j]=0;
    fscanf(f,"%d %d", &n, &m);
    for(i=0;i<m;i++)
    {
        fscanf(f,"%d%d", &x, &y);
        M[x][y]=M[y][x]=1;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            fprintf(g,"%d ", M[i][j]);
        fprintf(g,"\n");
    }
}

void DFS(Node *p[],int nod)
{
    Node *q;
    viz[nod]=1;
    for(q=p[nod]->next;q!=p[nod];q=q->next)
        if(viz[q->data]==0)
            DFS(p,q->data);

}*/

void Dijkstra(int n, FILE *g)
{
    int ok=0,i,poz_cost_minim,cost[50001],vizitat[50001],poz_curenta=1,j,min;
    for(i=1;i<=n;i++)
    {
        cost[i]=MAX;
        vizitat[i]=0;
    }
    cost[1]=0;
    Node *q;
    while(!ok)
    {
        ok=1;
        min=MAX;
        q=p[poz_curenta]->next;
        vizitat[poz_curenta]=1;
        while(q!=p[poz_curenta])
        {
            if(cost[poz_curenta]+q->length<cost[q->nod])
            {
                cost[q->nod]=cost[poz_curenta]+q->length;
                ok=0;
            }
            q=q->next;
        }
        for(j=1;j<=n;j++)
            if(!vizitat[j] && cost[j]<=min)
            {
                min=cost[j];
                poz_curenta=j;
            }
        for(i=1;i<=n;i++)
            printf("%d ", cost[i] );
        printf("\n");
    }
    for(i=2;i<=n;i++)
    {
        if(cost[i]==MAX)
            cost[i]=0;
        fprintf(g, "%d ", cost[i]);
    }
}
int main()
{
    FILE *f=fopen("dijkstra.in", "r");
    FILE *g=fopen("dijkstra.out", "w");
    int n,m,x,y,i,j,length;
    fscanf(f,"%d %d", &n, &m);
    for(i=1;i<=n;i++)
    {
        p[i]=(Node*)malloc(sizeof(Node));
        p[i]->next=p[i];
        p[i]->nod=0;
    }
    for(i=0;i<m;i++)
    {
        fscanf(f,"%d%d%d", &x ,&y, &length);
        adaugare_dupa(p[x],y, length);
    }
    Dijkstra(n,g);
   // for(i=1;i<=n;i++)
        //show(p[i],g);
    return 0;
}