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

FILE *f;
int d[30][30],cost[30][30];
typedef struct nodetype{
                            int val;
                            struct nodetype *urm;
                       }NodeT;


int main()
{    int n,i,j;
    citire(&n);
    printf("\nMatricea costurilor:\n");
 /*    for(i=1;i<=n;i++)
     { printf("\n");
         for(j=1;j<=n;j++)
         printf("%d ",cost[i][j]);
     }
*/
    floyd(n);

    return 0;
}

void citire(int *n)
 {
    int x,y,z,i,j;
    f=fopen("floyd.txt","r");
    fscanf(f,"%d",n);
    for(i=1;i<=*n;i++)
      for(j=1;j<=*n;j++)
      {
          if(i==j) cost[i][j]=0;
          else cost[i][j]=999;
          d[i][j]=-1;
      }
    while(!feof(f))
     {
         fscanf(f,"%d%d%d",&x,&y,&z);
         cost[x][y]=z;
         d[x][y]=x;
     }
 }

int floyd(int n)
 {
     int i,j,k,nodInitial,nodFinal;
     NodeT *p,*q,*p1;
     for(k=1;k<=n;k++)
      {
         for(i=1;i<=n;i++)
          for(j=1;j<=n;j++)
           {
               if(cost[i][j]>cost[i][k]+cost[k][j])
                {
                    cost[i][j]=cost[i][k]+cost[k][j];
                    d[i][j]=d[k][j];
                }
           }
      }

      printf("Introduceti nodul de pornire: "); scanf("%d",&nodInitial);
      printf("Introduceti nodul final: "); scanf("%d",&nodFinal);
      p=(NodeT*)malloc(sizeof(NodeT));
      q=(NodeT*)malloc(sizeof(NodeT));
      p->val=nodInitial;
      p->urm=q;
      q->val=nodFinal;
      q->urm=0;
      k=nodFinal;
      if(d[nodInitial][nodFinal]!=-1)
    {
      while(d[nodInitial][k]!=nodInitial)
       {
         k=d[nodInitial][k];
         p1=(NodeT*)malloc(sizeof(NodeT));
         p1->val=k;
         p->urm=p1;
         p1->urm=q;
         q=p1;
       }
                while(p)
                    {
                        printf("%d ",p->val);
                        p=p->urm;
                    }
                printf("\n");

    }
      else printf("\nNu exista drum intre cele 2 noduri!");
 }