/* 
   This is the program for shortest path problem using DP algorithm. 
   The cost of edges are assumed to be non-negative and a symmentryic
   graph is assumed as an input.
*/

#include <stdio.h>
#include <stdlib.h>
#define  INF       1000000
#define  ZERO      0.00001 

struct edge{
  double d;
  int    end1;
  int    end2;
}*E;

/*変数*/
int  width,  /*drawgraphでグラフを描画するときに横に並ぶ節点の個数*/
     n,      /*グラフの節点数*/
     m;      /*グラフの枝数*/

/*関数*/
void readin(void);               /*入力を読みこむ*/
void *malloc_e(size_t size);     /*メモリを確保する*/
int checkend(double **, int);    /*終了条件を判定する*/

void main(void){
  int i,k,curr,source,endstate;
  double **label;
  int  *prev,*check;

  /*read an input data and memory allocation*/
  readin();

  /*malloc for label[][], prev[] and check[]*/
  label = (double **)malloc_e(n*sizeof(double *));
  for(i=0;i<n;i++)
    label[i] = (double *)malloc_e(n*sizeof(double));
  prev = (int *)malloc_e(n*sizeof(int));
  check = (int *)malloc_e(n*sizeof(int));

  /*initialization of label[][] and prev[]*/
  source = 0;
  for(i=0;i<n;i++){
    label[i][0] = INF;
  }
  label[source][0] = 0.0;
  prev[source] = -1;

  /*DP starts. At the end of the kth step, label[v][k],v=0...n-1
   has been calculated, of which value means the shortest path length
   using at most k edges from the source.*/
  k = 1;
  while(1){
    for(i=0;i<n;i++)
      label[i][k] = label[i][k-1];
    for(i=0;i<m;i++){
      /*the case end1->end2*/
      if( label[E[i].end2][k] - (label[E[i].end1][k-1] + E[i].d) > ZERO ){
	label[E[i].end2][k] = label[E[i].end1][k-1] + E[i].d;
	prev[E[i].end2] = E[i].end1;
      }
      /*the case end2->end1*/
      if( label[E[i].end1][k] - (label[E[i].end2][k-1] + E[i].d) > ZERO ){
	label[E[i].end1][k] = label[E[i].end2][k-1] + E[i].d;
	prev[E[i].end1] = E[i].end2;
      }
    }
    if( ( endstate = checkend(label,k) ) != 0)    break;
    else                             k++;
  }

  if( endstate == -1 ){
    printf("there exists a negative cycle in the input graph.\n");
    printf("cannot construct the shortest path tree.\n");
    exit(EXIT_SUCCESS);
  }

  for(i=0;i<n;i++)
    check[i] = 0;

  for(i=n-1;i>0;i--){
    if( check[i] == 1 )   continue;
    curr = i;
    while( prev[curr] != -1 ){
      check[prev[curr]] = 1;
      curr = prev[curr];
    }
  }
}

void *malloc_e( size_t size ) {
  void *s;
  if ( (s=malloc(size)) == NULL ) {
    fprintf( stderr, "malloc : Not enough memory.\n" );
    fprintf( stderr, " -> Try setting cslub to -1.\n" );
    fprintf( stderr, "    If it fails, then try memeff = 1.\n" );
    exit( EXIT_FAILURE );
  }
  return s;
}


void readin(void){
  int i;

  fscanf(stdin,"%d %d %d",&width,&n,&m);
  E = (struct edge *)malloc_e(m*sizeof(struct edge));
  for(i=0;i<m;i++){
    fscanf(stdin,"%lf %d %d",&E[i].d, &E[i].end1, &E[i].end2);
    if( E[i].d - 1000000 >= ZERO ){
      fprintf(stderr,"ERROR:the cost of the edge %d->%d is too large!\n"
	      ,E[i].end1,E[i].end2);
      exit(EXIT_FAILURE);
    }
  }
}


int checkend(double **p, int k){
  int i,state=1;

  for(i=0;i<n;i++)
    if( p[i][k] != p[i][k-1] )
      state = 0;
  
  if( k == n && state == 0 )  return -1;
  else if( state == 0 )       return  0;
  else                        return  1;
}