3745 : Simplifying the Farm
- 제한시간
- 1000 ms
- 메모리제한
- 128 MB
- 해결횟수
- 0 회
- 시도횟수
- 0 회
문제
입력형식
* Line 1: Two integers N and M (1 <= N <= 40,000; 1 <= M <= 100,000), representing the number of vertices and edges in the farm graph, respectively. Vertices are numbered as 1..N.
* Lines 2..M+1: Three integers a_i, b_i and n_i (1 <= a_i, b_i <= N; 1 <= n_i <= 1,000,000) representing an edge from vertex a_i to b_i with length n_i. No edge length n_i will occur more than three times.
출력형식
* Line 1: Two integers representing the length of the minimal spanning tree and the number of minimal spanning trees (mod 1,000,000,007).
입력 예4 5 1 2 1 3 4 1 1 3 2 1 4 2 2 3 2 |
출력 예4 3 |
Hint!
* OUTPUT DETAILS:
Picking both edges with length 1 and any edge with length 2 yields a minimum spanning tree of length 4.