#include<stdio.h>

#include<malloc.h>
#define inf 300000
//conversie graf orientat neponderat din tabel in matrice
typedef struct
{
    int vf;
    int d;

}ETICHETA;

int citire_graf_n(char *numef,int *nrv,int *nrm , int ***g)
{
	FILE *f;
	int i,er;
	f=fopen("dijkstra.in","r");

	if (!f) er=1;
	else
	{
		er=0;
		fscanf(f,"%d %d" , nrv,nrm);
		//printf("%d %d \n\n ", *nrv,*nrm);
		*g=(int **)malloc(*nrm*sizeof(int*));
		  for (i=0;i<*nrm;++i)
			  (*g)[i]=(int*)malloc(3*sizeof(int*));

		  for(i=0;i<*nrm;++i)
		  {
			  fscanf (f,"%d %d %d" , &(*g)[i][0],&(*g)[i][1],&(*g)[i][2]);
			  //printf ("\n%d %d %d" , (*g)[i][0],(*g)[i][1],(*g)[i][2]);
		  }

		  fclose(f);
	}
	return er;
}


int **conversie(int nrv, int nrm, int **tabel, int *dim)
{
	int i,j;
	int **mat;
	*dim=nrv;
	mat=(int**)malloc(*dim*sizeof(int*));

	for  (i=0;i<*dim;i++)
		mat[i]=(int*)malloc(*dim*sizeof(int));

	for (i=0;i<*dim;i++)
		for (j=0;j<*dim;j++)
			mat[i][j]=0;

	for (i=0;i<nrm;i++)
	{
		mat[tabel[i][0]-1][tabel[i][1]-1]=tabel[i][2];
        mat[tabel[i][1]-1][tabel[i][0]-1]=tabel[i][2];
	}

	return mat;

}

ETICHETA *dijkstra (int n,int **a,int vp)
{
    int lmin,i,ui,vmin,*prel;

    prel=(int*)malloc(n*sizeof(int));
    ETICHETA *v=(ETICHETA*)malloc(n*sizeof(ETICHETA));


    vp--;


    for (i=0;i<n;++i) {prel[i]=0;v[i].d=inf;}
v[vp].d=0;
    prel[vp]=1;
ui=vp;

    for (int j=0;j<n-1;j++)
    {
        lmin=inf;

        for(i=0;i<n;++i)
        {

           // printf("\n prel=%d vi=%d vui=%d a=%d",prel[i],v[i].d,v[ui].d,a[ui][i]);
            if ((prel[i]==0)&&(v[i].d>v[ui].d+a[i][ui]))
            {
            v[i].d = v[ui].d+a[i][ui];
            v[i].vf = ui;
            }

             if ((prel[i]==0)&&(v[i].d < lmin))
             {
                 lmin=v[i].d;
                 vmin=i;
             }

        }
        ui=vmin;

        prel[ui]=1;

    }

        return v;


}




int main()
{
    FILE *g;
    g=fopen("dijkstra.out","w");
    char numefis[30];
    int n,m,**tabel , **a,dim ,er,i,j;
    er=citire_graf_n(numefis,&n,&m,&tabel);
	if (er==1) printf("Eroare deschidere fisier\n");
	a=conversie(n,m,tabel,&dim);
//printf("\n");
	for (i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
        {
        if (a[i][j]==0) a[i][j]=inf;
        //printf("%d ",a[i][j]);
        }
        //printf("\n");
    }

ETICHETA *rez=dijkstra(n,a,1);
//printf("\n");
for (i=1;i<n;++i)
    fprintf(g,"%d ",rez[i].d == inf ? 0 : rez[i].d);

fclose(g);


    return 0;
}