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

int nr_noduri;
int nr_arcuri;
int cost[1000][1000];
int dist[1000];
int tata[1000];
int vis[1000];


int main()
{
    FILE *f1 = fopen("dijkstra.in", "r");
    FILE *f2 = fopen("dijkstra.out", "w");

    int i, nod, vecin, nod1, nod2, val_cost;

    fscanf(f1, "%d%d", &nr_noduri, &nr_arcuri);
    for (i = 0; i < nr_arcuri; i++)
    {
        fscanf(f1, "%d%d%d", &nod1, &nod2, &val_cost);
        cost[nod1][nod2] = val_cost;
        //cost[nod2][nod1] = val_cost;
    }

    for (i = 0; i < nr_arcuri; i++)
    {
        dist[i] = 999999999;
    }

    dist[1] = 0;

    for (i = 1; i <= nr_noduri; i++)
    {
        int dist_min = 999999999;
        int nod_min = 0;

        for (nod = 1; nod <= nr_noduri; nod++)
        {
            if (vis[nod] == 0 && dist[nod] < dist_min)
            {
                dist_min = dist[nod];
                nod_min = nod;
            }
        }

        vis[nod_min] = 1;

        for (vecin = 1; vecin <= nr_noduri; vecin++)
        {
            if (vis[vecin] == 0 && cost[nod_min][vecin] > 0)
            {
                if (dist[vecin] > dist[nod_min] + cost[nod_min][vecin])
                {
                    dist[vecin] = dist[nod_min] + cost[nod_min][vecin];
                }
            }
        }
    }

    for (nod = 2; nod <= nr_noduri; nod++)
        fprintf(f2, "%d ", dist[nod]);
}