/* 単純法 */
#include <stdio.h>
#include <stdlib.h>
#define  INF       1000000

#define malloc_e(t, n)	(t*)malloc_e_void((unsigned)(sizeof(t)*(n)))

/* struct edge 型の定義 */
struct edge{
  int d;
  int end1, end2;
};

/* struct graph 型の定義 */
struct graph{
  int width; /* drawgraphでグラフを描画するときに横に並ぶ節点の個数 */
  int n;     /* 節点数 */
  int m;     /* 枝数 */
  struct edge *E;
};

/* エラーチェック付き malloc; 返り値は void* 型 */
void*
malloc_e_void(size_t size) {
  void *ptr = malloc(size);
  if (!ptr) {
    fprintf(stderr, "malloc : Not enough memory.\n" );
    exit(EXIT_FAILURE);
  }
  return ptr;
}

/* データの読み込み */
void read(struct graph *gp){
  int e;
  
  fscanf(stdin, "%d %d %d", &gp->width, &gp->n, &gp->m);
  gp->E = malloc_e(struct edge, gp->m);
  for (e = 0 ; e < gp->m; e++){
    fscanf(stdin, "%d %d %d", &gp->E[e].d, &gp->E[e].end1, &gp->E[e].end2);
    if(gp->E[e].d >= INF){
      fprintf(stderr, "ERROR: the cost of the edge %d->%d is too large!\n",
	      gp->E[e].end1, gp->E[e].end2);
      exit(EXIT_FAILURE);
    }
  }
}

/* drawgraph.tcl 用グラフ定義の出力 */
void
write(struct graph *gp, int source){
  int e;
  printf("### graph definition\n");
  printf("begingraph\n");
  printf("width     %d\n", gp->width);
  printf("nodenum   %d\n", gp->n);
  printf("edgenum   %d\n", gp->m);
  printf("source    %d\n", source);
  printf("nodestart 0\n");
  printf("# edges\n");
  for (e = 0; e < gp->m; e++){
    printf("edge %d %d %d\n", 	gp->E[e].d, gp->E[e].end1, gp->E[e].end2);
  }
  printf("endgraph\n###\n");
}


/* main 関数 */
int 
main(int argc, char *argv[]){
  int v, e, k, source;
  int **label;
  int *prev;
  struct graph g;

  /* source: 実行時，引数を省略すれば 0 */
  if (argc > 1) source = atoi(argv[1]);
  else source = 0;

  /* データの読み込み & メモリ確保 */
  read(&g);
  if (source < 0 || source >= g.n){
    fprintf(stderr, "ERROR: invalid source number.\n");
    exit(EXIT_FAILURE);
  }

  /* drawgraph.tcl 用グラフ定義部分の出力 */
  write(&g, source);

  /* malloc for label[][], prev[] */
  label = malloc_e(int*, g.n);
  for (v = 0; v < g.n; v++) label[v] = malloc_e(int, g.n+1);
  prev = malloc_e(int, g.n);
  
  /* 初期化: label[][] and prev[] */
  for (v = 0; v < g.n; v++){
    label[v][0] = INF;
    prev[v] = -1;
  }
  label[source][0] = 0;
 
  /* At the end of the k-th step, label[v][k], v= 0, 1, ..., n-1, has been 
     calculated, whose value means the shortest path length using at most 
     k edges from the source.*/
  k = 1;
  while(1){
    for(v = 0; v < g.n; v++) label[v][k] = label[v][k-1];

    printf("step # k = %d\n", k);
    for(v = 0; v < g.n; v++){
      printf("label %d %d\n", v, label[v][k]);
      printf("colornode %d white\n", v);
      if (prev[v] >= 0) printf("coloredge %d %d red\n", v, prev[v]);
    }
    
    printf("step\n");
    for(e = 0; e < g.m; e++){
      int flag = (prev[g.E[e].end1] == g.E[e].end2 ||
		  prev[g.E[e].end2] == g.E[e].end1);
      if (flag) printf("coloredge %d %d pink\n", g.E[e].end1, g.E[e].end2);
      else printf("coloredge %d %d grey\n", g.E[e].end1, g.E[e].end2);
      printf("step\n");

      /* the case end1->end2 */
      if(label[g.E[e].end2][k] > label[g.E[e].end1][k-1] + g.E[e].d){
	label[g.E[e].end2][k] = label[g.E[e].end1][k-1] + g.E[e].d;
	printf("colornode %d red\n", g.E[e].end2);
	if (prev[g.E[e].end2] >= 0){
	  printf("coloredge %d %d black\n", prev[g.E[e].end2], g.E[e].end2);
	}
	prev[g.E[e].end2] = g.E[e].end1;
	flag = 2;
      }

      /* the case end2->end1 */
      if(label[g.E[e].end1][k] > label[g.E[e].end2][k-1] + g.E[e].d){
	label[g.E[e].end1][k] = label[g.E[e].end2][k-1] + g.E[e].d;
	printf("colornode %d red\n", g.E[e].end1);
	if (prev[g.E[e].end1] >= 0){
	  printf("coloredge %d %d black\n", prev[g.E[e].end1], g.E[e].end1); 
	}
	prev[g.E[e].end1] = g.E[e].end2;
	flag = 2;
      }

      if (flag == 0){
	printf("coloredge %d %d black\n", g.E[e].end1, g.E[e].end2);
      }
      else if (flag == 1){
	printf("coloredge %d %d red\n", g.E[e].end1, g.E[e].end2);
      }
      else {
	printf("coloredge %d %d orange\n", g.E[e].end1, g.E[e].end2);
      }
    }

    /* 終了条件の判定 */
    for (v = 0; v < g.n; v++){
      if(label[v][k] != label[v][k-1]) break;
    }
    if (v == g.n) break; /* label[v][k] == label[v][k-1], for all v */
    if (k == g.n){
      printf("there exists a negative cycle in the input graph.\n");
      printf("cannot construct the shortest path tree.\n");
      exit(EXIT_SUCCESS);
    }
    k++;
  }
  printf("end\n");

  /* 最短路の出力 */
  for(v = 0; v < g.n; v++){
    int curr = v;
    printf("# ");
    while( prev[curr] != -1 ){
      printf("%d <-- ", curr);
      curr = prev[curr];
    }
    printf("%d (length = %d)\n", source, label[v][k]);
  }
  exit(EXIT_SUCCESS);
}