import java.util.*;

/**
* 用堆实现了从一个点到其他点的最短路径
* @author
*/
public class ShortestPath
{
/**有n个节点*/
private int n;
/**节点矩阵*/
private double matrix[][] = null;
/**存储单源最短路径*/
private double minpath[];

public ShortestPath(int n)
{
this.n = n;
matrix = new double[n+1][n+1];
minpath = new double[n+1];

for(int i=1;i<=n;i++)
{
minpath[i] = Double.MAX_VALUE;
}

//初始化图
getGraphMatrix();
}

/**
* 构造图的矩阵(带权有向图)
*/
public void getGraphMatrix()
{
//初始化为不能连通
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
matrix[i][j] = Double.MAX_VALUE;
}
}

System.out.println("有多少条边？");
Scanner scan = new Scanner(System.in);

int m = scan.nextInt();

System.out.println("依次输入两个顶点号(1~"+n+")和边长:例如 1 2 3");
for(int i=0;i<m;i++)
{
int a,b;
double d;
a = scan.nextInt();
b = scan.nextInt();
d = scan.nextDouble();
if(a<1 || b<1)
{
i--;
System.out.println("顶点号不能小于1");
continue;
}
if(a>n||b>n)
{
i--;
System.out.println("顶点号不能大于"+n);
continue;
}
matrix[a][b] = d;
}
}

/**
*@param 求以第i个节点为起点的单源最短路径
*/
public void shortpath(int i)
{
minpath[i] = 0;

double curlen = 0;

PriorityQueue<Node> heap = new PriorityQueue();
Node cur = new Node(i,0);
heap.add(cur);

while(!heap.isEmpty())
{
for(int j=1;j<=n;j++)
{
if(matrix[cur.i][j]<Double.MAX_VALUE && cur.len+matrix[cur.i][j]<minpath[j])
{
minpath[j] = cur.len+matrix[cur.i][j];
heap.add(new Node(j,minpath[j]));
}
}
cur = heap.poll();
}

//打印最短路径结果
for(int j=1;j<=n;j++)
{
if(minpath[j]<Double.MAX_VALUE && j!=i)
{
System.out.println("最短路径：");
System.out.println(i+"到"+j+":"+minpath[j]);
}

}
}

public static void main(String args [])
{
ShortestPath s = new ShortestPath(6);
s.shortpath(6);
}
}

/**
* 定义拥有自然顺序（Comparable）的节点用于优先队列
* @author 
*/
class Node implements Comparable<Node>
{
int i;
double len;
public Node(int i,double l)
{
this.i = i;
len = l;
}

public int compareTo(Node o)
{
double dif = len-o.len;
if(dif>0)
{
return 1;
}
else if(dif==0)
{
return 0;
}
else
{
return -1;
}
}

}