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

#include "prioridade.h"
#define INF 100

int main() {
  filaPrior * f; 
  int i, n, m, j, u, v, cuv, a[50][50], d[50][50], dist[50]; 
  item novo; 
  
  /* lê grafo */ 
  scanf("%d %d", &n, &m); 
  f = criaFilaPrior (1, n); 
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      a[i][j] = 0;
  for (i = 0; i < m; i++){
    scanf("%d %d %d", &u, &v, &cuv);
    a[u][v] = 1;     /* tem ligação entre u e v */
    d[u][v] = cuv;   /* custo desta ligação */ 
  } 

  /* inicializa as disr=tâncias com infinito e a distância de s com 0 */
  for (i = 0; i < n; i++) dist[i] = INF; 
  dist[0] = 0;
  novo.elem = 0;
  novo.prior = 0;

  /* insere s na fila de prioridade */

  insere (f, novo); 
  while (!filaPriorVazia (f)){
    u = removeMinimo (f);     
    for (v = 0; v < n; v++)
      if (a[u][v] == 1 && dist[v] == INF){  /* se v é vizinho de u e não tinha caminho */ 
        dist[v] = dist[u] + d[u][v]; 
        novo.elem = v;
        novo.prior = dist[v]; 
        insere (f, novo); 
      } 
      else if (a[u][v] == 1 && dist[v] > dist[u] + d[u][v]){ /* se v é vizinho e a distância por u fica menor */ 
        dist[v] = dist[u] + d[u][v]; 
        mudaPrior (f, v, dist[v]);
      }

  }
  printf("dist: "); 
  for (u = 0; u < n; u++) 
    printf("%3d ", dist[u]);
  printf("\n");
  

  return 0;
}