/* 
   枝についているコストが非負であるグラフの最短路問題を解くプログラム.
   ダイクストラ法を実装. データ構造にヒープを用いていないので,
   時間量はO(m + n^2).
*/

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

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

struct node{
  int nodenum;
  int edgenum;  
  struct node *next;
}*V;

struct cost{
  double d;
  int    prev;
}*label;

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

/*関数*/
int findminnode(int *, int *);  /*最短路が決定されていない節点の内暫定コストが最小である節点を返す関数*/
void readin(void);              /*データの入力のための関数*/
void *malloc_e(size_t size);    /*メモリ確保のための関数*/
void make_adjlist(void);        /*接続リストを作成する関数*/
void initialization(int *,int *,int *,int *);      /*初期化を行う関数*/

void main(void){ 
  int  i,
       source,      /*この変数の値である節点からの最短路を求めていく.
                      プログラム中では 0 に設定*/
       NumLeftNode, /*最短路が決定されていない節点の個数を格納. この値が0になるとプログラムは終了*/
       *nodestate,  /*節点の状態を表す.
		       1  暫定コストがINF以外になっている
		       0  暫定コストがINF
		      -1  最短路が求められている*/
       *prev,       
       minnode;     /*暫定コストが最小のとなる節点番号を覚えるための変数*/
  struct node  *pt; 

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

  /*memory allocation*/
  label = (struct cost *)malloc_e(n*sizeof(struct cost));
  nodestate = (int *)malloc_e(n*sizeof(int));
  prev = (int *)malloc_e(n*sizeof(int));

  /*construct an adjacent list*/
  make_adjlist();

  /*initialization*/
  initialization(prev,nodestate,&source,&NumLeftNode);
  
  while( NumLeftNode != 0 ){
    minnode = findminnode(nodestate,prev);
    nodestate[minnode] = -1;
    NumLeftNode--;

    for(pt=V[minnode].next ; pt!=0 ; pt=pt->next){
      if( nodestate[pt->nodenum] != -1 ){
	nodestate[pt->nodenum] = 1;
      }
      else{ continue; }
      
      if( label[pt->nodenum].d - (label[minnode].d + E[pt->edgenum].d) > ZERO ){
	label[pt->nodenum].d = label[minnode].d + E[pt->edgenum].d;
	label[pt->nodenum].prev = minnode;
      }
    }
  }

  for(i=0;i<n;i++){
    int pt;
    printf("node:%d\tcost:%.0f\t%d",i,label[i].d,i);
    for(pt=prev[i] ; pt!=-1 ; pt=prev[pt]){
      printf("<-%d",pt);
    }
    printf("\n");
  }
}

int findminnode(int *flag, int *prev){
  int i,nodenow = -1;
  double costnow = (double)INF;

  for(i=0;i<n;i++){
    if( flag[i] != 1 )  continue;
    if( label[i].d - costnow < ZERO ){
      nodenow = i;
      costnow = label[i].d;
    }
  }

  if( nodenow == -1 ){
    fprintf(stderr,"error in findminnode!!\n");
    exit(EXIT_FAILURE);
  }

  prev[nodenow] = label[nodenow].prev;
  return nodenow;
}


void readin(void){
  int i;

  fscanf(stdin,"%d %d %d ",&width,&n,&m);
  /*memory allocation for edge data*/
  E = (struct edge *)malloc_e(m*sizeof(struct edge));
  /*input the edge data*/
  for(i=0;i<m;i++)
    fscanf(stdin,"%lf %d %d",&E[i].d,&E[i].end1,&E[i].end2);
}


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 make_adjlist(void){
  int i;
  struct node  **curr,*new;

  V = (struct node *)malloc_e(n*sizeof(struct node));
  curr = (struct node **)malloc_e(n*sizeof(struct node *));
  for(i=0;i<n;i++){
    V[i].next = NULL;
    curr[i] = &V[i];
  }

  for(i=0;i<m;i++){
    new = (struct node *)malloc_e(sizeof(struct node));
    new->nodenum = E[i].end2;
    new->edgenum = i;
    new->next = NULL;
    curr[E[i].end1]->next = new;
    curr[E[i].end1] = new;
    new = (struct node *)malloc_e(sizeof(struct node));
    new->nodenum = E[i].end1;
    new->edgenum = i;
    new->next = NULL;
    curr[E[i].end2]->next = new;
    curr[E[i].end2] = new;
  }
}

void print_graph(void){
  int i;

  printf("begingraph\n");
  printf("width\t%d\n",width);
  printf("nodenum\t%d\n",n);
  printf("edgenum\t%d\n",m);
  printf("source\t0\n");
  printf("nodestart\t0\n");
  for(i=0;i<m;i++)
    printf("edge\t%.0f\t%d\t%d\n",E[i].d,E[i].end1,E[i].end2);
  printf("endgraph\n");
}

void initialization(int previous[], int state[], int *s, int *Num){
  int i;
  struct node  *pt;

  *s = 0;
  *Num = n - 1;
  for(i=0;i<n;i++){
    label[i].d = (double)INF;
    state[i] = 0;
  }

  previous[0] = -1;
  state[0] = -1;
  label[0].d = 0.0;

  for(pt=V[0].next ; pt!=NULL ; pt=pt->next){
    state[pt->nodenum] = 1;
    label[pt->nodenum].d = E[pt->edgenum].d;
    label[pt->nodenum].prev = 0;
  }
}