//Algoritmul drumurilor minime al lui Dijkstra
#include<stdio.h>
int S[1000]={0}, T[1000]={0}, D[1000]={0}, N, M;
short int ma[1000][1000];
void dijkstra(int rad)
{
    FILE *out;
    out=fopen("dijkstra.out", "w");
    int i, j, poz, min;
    S[rad]=1;
    for(i=0; i<N; i++)
    {
        D[i]=ma[rad][i];
        if (rad!=i && D[i]<10000)
            T[i]=rad;
    }
    for(i=0; i<N-1; i++)
    {
        min=10000;
	for(j=0; j<N; j++)
            if(S[j]==0)
		if(D[j]<min)
                {
                    min=D[j];
                    poz=j;
                }
         S[poz]=1;
         for(j=0;j<N;j++)
            if(S[j]==0)
                if(D[j]>D[poz]+ma[poz][j])
                {
                    D[j]=D[poz]+ma[poz][j];
                    T[j]=poz;
                }
    }
    for (i=0; i<N; i++)
        if (rad!=i)
            if (D[i]==1001)
                fprintf(out, "0 ");
            else
                fprintf(out, "%i ", D[i]);
    fclose(out);
}
int main()
{
    FILE *in;
    in=fopen("dijkstra.in", "r");
    int x, y, i, c, j;
    fscanf(in, "%i %i", &N, &M);
    for (i=0; i<N; i++)
        for (j=0; j<N; j++)
            ma[i][j]=1001;
    for (i=0; i<M; i++)
    {
        fscanf(in, "%i %i %i", &x, &y, &c);
        x--;
        y--;
        ma[x][y]=c;         //este graf orientat asa ca nu fac si ma[y][x]=1;
    }
    fclose(in);
    dijkstra(0);
    return 0;
}