#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
struct arc
{
    int x,y;
    double c;
}A[250000];
const double pinf = 1.e20;
double d[500];
int t[500], n,r,m,circuit;
ofstream g("graf.out");

void drum(int i)
{
    if(t[i]) drum(t[i]);
    g<<i<<" ";
}

void citire()
{
    int i,j;
    double c;
    ifstream f("graf.in");
    f>>n;
    while(f>>i>>j>>c)
    {
        m++;
        A[m].x=i;A[m].y=j;A[m].c=c;
    }
    f.close();
}
void init_d()
{
    int i;
    for(i=1;i<=n;i++) d[i]=pinf;
}
void Ford()
{
    int i,j,c,k,kk,gata;
    init_d(); // initializam toate drumurile de la r cu pinf
    d[r]=0; gata=0;
    for(kk=1;kk<=n-1 && !gata;kk++)
    {
       gata=1;
       for(k=1;k<=m;k++)  //parcurgem toate cele m muchii
       {
          i=A[k].x; j=A[k].y; c=A[k].c;
          if( d[j]>d[i]+c)
          {
             d[j]=d[i]+c; t[j]=i;
             gata=0;
          }
      }
    }
//verificam daca graful contine sau nu vreun circuit de cost negativ
    if(!gata) // in cea de-a (n-1)-a parcurgere s-au facut optimizari
    circuit=0;
    for(k=1;k<=m;k++)
    {
       i=A[k].x; j=A[k].y; c=A[k].c;
       if(d[j]>d[i]+c) circuit=1;
    }
}
int main()
{
    int i;
    citire();
    cout<<"introduceti nodul sursa:";cin>>r;
    Ford();
    if(circuit)g<<"graful contine un circuit negativ ";
    else
     for(i=1;i<=n;i++){// g<<d[i]<<endl;
       if(i!=r && d[i]<pinf)
       {
          g<<r<<"->"<<i<<": "<<d[i]<<", drumul: ";
          drum(i);
          g<<endl;
       }}
    return 0;
}