memo dijkstra

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>

const int INF = 10000;

using namespace std;

// struct edge { int to ,cost; };

struct edge {
  int to, cost;
  edge(int _to, int _cost) {to = _to; cost=_cost;}
};

typedef pair<int ,int>P;

int V;

vector<edge> G[8];

int d[8];

void dijkstra(int s ){

  priority_queue<P,vector<P>,greater<P> > que;
  fill (d,d + V,INF);
  d[s] = 0;
  que.push(P(0,s));

  while(!que.empty()){

    P p = que.top(); que.pop();
    int v = p.second;
    if (d[v] < p.first) continue;
    for(int i = 0;i < G[v].size();i++){
      edge e = G[v][i];
      if(d[e.to] > d[v] + e.cost){
	d[e.to] = d[v] + e.cost;
	que.push(P(d[e.to], e.to));
      }
    }
  }
}


int main(){

  int tmp = 0;

  scanf("%d%d",&V,&tmp);

  for(int i = 0;i < tmp;i++){
    int a1,a2,a3;
    scanf("%d%d%d",&a1,&a2,&a3);
    G[a1].push_back(edge(a2,a3));
    G[a2].push_back(edge(a1,a3));
    //    G[a1][a2] = a3;

  }

  dijkstra(0);

  printf("%d\n",d[6]);

  return 0;

}