#include <stdio.h>
#include <stdlib.h>

#define NRMAXNODURI 2000
#define INF 999999998

#define IN "dijkstra.in"
#define OUT "dijkstra.out"

typedef struct
{
    int nrNoduri;
    int matAdiacenta[NRMAXNODURI][NRMAXNODURI];
    int matCost[NRMAXNODURI][NRMAXNODURI];
    int Drum[NRMAXNODURI];
    int Traseu[NRMAXNODURI];
    int vizitat[NRMAXNODURI];
} Graf;

 Graf graf;

void initGraf(Graf *g)
{
    g->nrNoduri = 0;
    for (int i = 0; i < NRMAXNODURI; i++)
    {
        g->Drum[i] = 0;
        g->Traseu[i] = 0;
        g->vizitat[i] = 0;
        for (int j = 0; j < NRMAXNODURI; j++)
        {
            g->matAdiacenta[i][j] = 0;
            if (i != j)
            {
                g->matCost[i][j] = INF;
            }
            else
            {
                g->matCost[i][j] = 0;
            }
        }
    }
}

void adaugaArcOrientat(Graf *g, int i, int j, int pondere)
{
    g->matAdiacenta[i][j] = pondere;
    g->matCost[i][j] = pondere;
}

void dijkstra(Graf *g, int indexNod)
{
    for(int i = 0; i < g->nrNoduri; i++)
    {
        g->Drum[i] = g->matCost[indexNod][i];
        g->Traseu[i] = indexNod;
    }

    g->Drum[indexNod] = 0;
    g->Traseu[indexNod] = indexNod;
    g->vizitat[indexNod] = 1;

    for(int i = 0; i < g->nrNoduri; i++)
    {
        int minim = INF + 1, minI = -1;
        for(int j = 0; j < g->nrNoduri; j++)
        {
            if(g->vizitat[j] == 0 && g->Drum[j] < minim)
            {
                minim = g->Drum[j];
                minI = j;
            }
        }
        if(minI != -1)
        {
            g->vizitat[minI] = 1;
            for(int k = 0; k < g->nrNoduri; k++)
            {
                if(g->vizitat[k] == 0 && minim + g->matCost[minI][k] < g->Drum[k])
                {
                    g->Drum[k] = minim + g->matCost[minI][k];
                    g->Traseu[k] = minI;
                }
            }
        }
    }
}

int main(void)
{
    FILE *in, *out;
    in = fopen(IN, "r");
    out = fopen(OUT, "w");

    int nrMuchii, i, j, pondere;

    initGraf(&graf);

    fscanf(in, "%d", &graf.nrNoduri);
    fscanf(in, "%d", &nrMuchii);
    for (int k = 0; k < nrMuchii; k++)
    {
        fscanf(in, "%d %d %d", &i, &j, &pondere);
        adaugaArcOrientat(&graf, i - 1, j - 1, pondere);
    }

    dijkstra(&graf, 0);
    for(int i = 1; i < graf.nrNoduri; i++)
    {
        fprintf(out, "%d ", graf.Drum[i]);
    }

    fclose(in);
    fclose(out);
    return 0;
}