# Poj Solution 3159

```http://poj.org/problem?id=3159

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;

class node implements Comparable{
int v,next,disten;
node(){
v = next = disten = -1;
}
node(int v,int next,int disten){
this.v = v;
this.next = next;
this.disten = disten;
}
void set_node(int v,int next,int disten){
this.v = v;
this.next = next;
this.disten = disten;
}
void copy(node obj){
this.v = obj.v;
this.next = obj.next;
this.disten = obj.disten;
}
public int compareTo(Object obj){

node cnt = (node)obj;
if(cnt.disten< disten) return 1;
return -1;
}
}
class binary_Heap{
node tree[];
int n,p,c;
binary_Heap(){};
binary_Heap(int cap){
n = 0;
tree = new node[40000];
for(int i=0;i< 40000;++i) tree[i] = new node();
}
void push(node temp){
for(p=++n;p>1 && tree[p>>1].compareTo(temp)>0;p>>=1){
tree[p].copy(tree[p>>1]);
}
tree[p].copy(temp);

}
node front(){return tree[1];}
void pop(){
for(p=1,c=2;c< n && tree[c+=(c< n-1 && tree[c+1].compareTo(tree[c])>0)?1:0].
compareTo(tree[n])>0;tree[p].copy(tree[c]),p=c,c<<=1);

tree[p].copy(tree[n--]);
}
}
class Graph{
int n,top;
node Map[];
Graph(){}
Graph(int n){
top = n+1;
this.n = n;
Map = new node[200000];
for(int i=0;i< 200000;++i){
Map[i] = new node();
}
}
Map[top].set_node(v, Map[u].next,disten);
Map[u].next = top;
++top;
}

int get_Dijkstra(int s,int t){
node temp = new node();
int BIG = 1000000000;
int meat[] = new int[n+10];
//binary_Heap heap = new binary_Heap(n);
Queue que = new PriorityQueue< node>();

Arrays.fill(meat, BIG);

meat[s] = 0;
for(int i=Map[s].next;i>=0;i=Map[i].next){
meat[Map[i].v] = Map[i].disten;

//heap.push(Map[i]);
}
//while(heap.n>0){
while(!que.isEmpty()){
//temp.copy(heap.front());
temp.copy((node)que.element());
que.remove();
//    heap.pop();

if(meat[temp.v]==temp.disten){
for(int i=Map[temp.v].next;i>=0;i=Map[i].next){
if(meat[Map[i].v]>temp.disten+Map[i].disten){
meat[Map[i].v] = temp.disten+Map[i].disten;
//heap.push(new node(Map[i].v,-1,meat[Map[i].v]));
}
}
}
}

return meat[t];
}
}

public class Main {

static public void main(String[]args)throws Exception{

int n,m,u,v,disten;
Graph obj;

n = Get_Num(cin);
m = Get_Num(cin);

obj = new Graph(n);

for(int i=0;i< m;++i){
u = Get_Num(cin);
v = Get_Num(cin);
disten = Get_Num(cin);