9117: Puzzle: Kurodoko (Max)
内存限制：128 MB
时间限制：1 S
题面：传统
评测方式：文本比较
上传者：
提交：0
通过：0
题目描述
Grammy is a puzzle master. Today, she is playing a variant of "Kurodoko" puzzle.
The puzzle consists of a graph with nnn vertices and mmm undirected edges. Each vertex has a clue value aia_iai, and each edge has a length lil_ili.
The goal is to find a spanning tree such that for each vertex, the distance to its furthest point on the spanning tree is exactly its clue value aia_iai.
The left picture illustrates an empty puzzle, and the right picture shows a solution to the puzzle.
Grammy surely knows how to solve the puzzle, but she decided to give you a quiz. Please solve the puzzle.
The puzzle consists of a graph with nnn vertices and mmm undirected edges. Each vertex has a clue value aia_iai, and each edge has a length lil_ili.
The goal is to find a spanning tree such that for each vertex, the distance to its furthest point on the spanning tree is exactly its clue value aia_iai.
The left picture illustrates an empty puzzle, and the right picture shows a solution to the puzzle.
Grammy surely knows how to solve the puzzle, but she decided to give you a quiz. Please solve the puzzle.
输入格式
The first line contains two integers n,mn,mn,m (2≤n≤105,n−1≤m≤2×1052 \leq n \leq 10^5, n-1 \leq m \leq 2 \times 10^52≤n≤105,n−1≤m≤2×105), denoting the number of vertices and the number of edges.
The next line contains nnn integers aia_iai(1≤ai≤1091 \leq a_i \leq 10^91≤ai≤109), denoting the clue values of the vertices.
Each of the following mmm lines contains 333 integers ui,vi,liu_i, v_i, l_iui,vi,li(1≤ui,vi≤n,1≤li≤1041 \leq u_i,v_i \leq n, 1 \leq l_i \leq 10^41≤ui,vi≤n,1≤li≤104), denoting an edge of length lil_ili connecting vertex uiu_iui and vertex viv_ivi.
It is guaranteed that the graph is connected. Note that the graph may contain self-loops and/or multiple edges.
The next line contains nnn integers aia_iai(1≤ai≤1091 \leq a_i \leq 10^91≤ai≤109), denoting the clue values of the vertices.
Each of the following mmm lines contains 333 integers ui,vi,liu_i, v_i, l_iui,vi,li(1≤ui,vi≤n,1≤li≤1041 \leq u_i,v_i \leq n, 1 \leq l_i \leq 10^41≤ui,vi≤n,1≤li≤104), denoting an edge of length lil_ili connecting vertex uiu_iui and vertex viv_ivi.
It is guaranteed that the graph is connected. Note that the graph may contain self-loops and/or multiple edges.
输出格式
If the solution does not exist, output "NO\texttt{NO}NO" on a single line. Otherwise, output "YES\texttt{YES}YES" on the first line, then output n−1n-1n−1 lines, each of which contains 333 integers ui,vi,liu_i, v_i, l_iui,vi,li, denoting an edge in the final spanning tree. If there are multiple solutions, output any.
输入样例 复制
5 7
8 4 5 6 8
1 2 3
1 3 3
2 3 1
2 4 2
3 4 3
2 5 4
4 5 2输出样例 复制
YES
2 3 1
2 5 4
3 1 3
2 4 2