Matcom Online Grader

PLand es un país con n ciudades y m caminos. Cada camino conecta un par de ciudades distintas y es bidireccional. Por cada camino concemos su distancia. Tambien sabemos que el rey pronto viajará por los caminos de PLand desde la ciudad s hasta la ciudad t , naturalmente el viajará por una de las rutas mínimas de s a t , pero nadie sabe cual eligirá. El Ministro de Transporte no quiere que el Rey vea el estado de los caminos de PLand, por lo cual planea arreglar varios de los posibles caminos por los cuales viajará el Rey. Hacer las cuentas para este proceso es complicado, por lo que el ministro desea saber para todos los pares s , t ( s < t ) la cantidad de caminos que pertenecen a al menos una ruta minima entre s y t .

La primera línea de la entrada contiene dos enteros n y m (2 ≤ n ≤ 500,0 ≤ m ≤ n∗(n−1)/2), la cantidad de ciudades y caminos respectivamente. Luego seguirán m líneas conteniendo la descripción de los caminos, cada descripción son tres enteros Xi,Yi,Wi, (Xi != Yi),1 ≤ Wi ≤ 10^6, donde Xi,Yi son los números de las ciudades conectadas por el camino i-ésimo y Wi es su distancia.

Imprima una secuencia de n ∗ (n − 1)/2 entros C12,C13,...,C1n,C23,C24,...,C2n,...,Cn−1,n donde Cst es el número de caminos que pertenecen a al una ruta mínima entre s y t . Imprima los elementos en el orden indicado, si dos pares de ciudades no tienen un camino entre ellas imprima 0.