Detour
시간 제한5초메모리 제한1024 MB
각 간선마다 그 간선을 사용하지 않고 양 끝점을 잇는 최단 경로의 길이를 구한다.
문제
In the city of Nlogonia, the mayor is taking action on his promises to revitalize the city’s road infrastructure. However, the road renewal process renders certain roads temporarily impassable, requiring the establishment of detours to ensure uninterrupted traffic flow.
Each road segment connects two crossroads in the city, has a positive length and can be traversed in both directions. A detour is a designated alternative route that temporarily replaces a road segment under renewal. Specifically, when the road connecting crossroads U and V is impassable, the detour must be a sequence of roads that originates at U and terminates at V , while intentionally avoiding the direct road between U and V . The goal is to find the shortest detour for each road segment to minimize disruptions while road improvements take place.
As the Intern at the Center for Pavement and Cars, your responsibility is to support the mayor’s initiative by calculating the length of the shortest detour for each road segment within the city.
입력
The first line contains two integers, N and M (1 ≤ N ≤ 300), representing the number of crossroads in the city and the number of road segments. Each of the following M lines contains three integers, U, V , and L (1 ≤ U ≤ N, 1 ≤ V ≤ N, U ≠ V , 1 ≤ L ≤ 106), representing a two-way road segment of length L that connects crossroads U and V. No road segment is duplicated.
출력
Output M lines, each line containing an integer. The integer on the i-th line represents the shortest detour length for the i-th road segment or -1 if there is no possible detour. The answer for each road segment should be given in the same order as road segments are described in the input.