Poj Solution 1511

http://poj.org/problem?id=1511

//* @author: 82638882@163.com
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main
{
 static int[] cost;
 static node[] edge,redge;
 static int n;
 static boolean[] used;
 public static void main(String[] args) throws NumberFormatException, IOException
  {
   InputStreamReader is=new InputStreamReader(System.in);
   BufferedReader in=new BufferedReader(is);
   int h=Integer.parseInt(in.readLine());
   while((h--)!=0)
   {
    String[] ss=in.readLine().split(" ");
    n=Integer.parseInt(ss[0]);
    edge=new node[n];
    redge=new node[n];
    cost=new int[n];
    used=new boolean[n];
    for(int i=0;i< n;i++)
    {
        edge[i]=new node(-1,-1);
        redge[i]=new node(-1,-1);
    }
    int m=Integer.parseInt(ss[1]);
    for(int i=0;i< m;i++)
    {
        ss=in.readLine().split(" ");
        int x=Integer.parseInt(ss[0]);
        int y=Integer.parseInt(ss[1]);
        int w=Integer.parseInt(ss[2]);
        insert(x,y,w);
    }
    long w=0;
    w+=spfa(0);
    w+=spfa(1);
    System.out.println(w);
   }
  }

  static void insert(int x,int y,int w)
  {
    x--;y--;
    node temp=new node(y,w);
    temp.next=edge[x].next;
    edge[x].next=temp;
    temp=new node(x,w);
    temp.next=redge[y].next;
    redge[y].next=temp;    
   }

  static long spfa(int d)
  {
   node temp;
   for(int i=0;i< n;i++)
    cost[i]=2000000000;
   Queue< Integer> qu=new LinkedList< Integer>();
   qu.add(0);
   cost[0]=0;
   while(!qu.isEmpty())
   {
    int u=qu.poll();
    used[u]=false;
    if(d==0)temp=edge[u].next;
    else temp=redge[u].next;
    while(temp!=null)
    {
        if(cost[temp.v]>cost[u]+temp.w)
        {
          cost[temp.v]=cost[u]+temp.w;
          if(!used[temp.v])
          {
            qu.add(temp.v);
            used[temp.v]=true;
          }
        }
        
        temp=temp.next;
    }
   }
  long ans=0;
  for(int i=0;i< n;i++)
    ans+=cost[i];
  return ans;
 }
    
}

class node
{
    int v,w;
    node next=null;
    public node(int vv,int ww)
    {
        v=vv;w=ww;
    }
}