Background

::::info[A Love Poem (Unrelated to the Problem)]{open}

Hearts linked, the nodes’ thoughts linger on, love tied to edges, the longing never gone.

qzw hides deep feelings, like aged wine, hyt’s graceful shadow stays in mind.

Egret City’s warm breeze smooths the frown, Xunwei’s light mist locks soft sorrow down.

In this life I wish to chase longing long, together from dawn to dusk we roam.

:::align{right} ——Ayton_Will ::::

::::info[Another Poem (Unrelated to the Problem)]{open}

This problem is adapted by me from an impossible problem by Brother Ayton. One day during training, I may have sighed that it achieved nothing, but that is not the truth. Besides, I happened to be in the position of the problem setter, so I wrote this piece to show it to the world.

A strange problem began, stuck and unclear, one stream of inspiration, I felt your work sincere.

With brush in hand, alone you carved dense lines, through the fog we opened, all things aligned.

Old trees, roots coiled, the red sun slants, lush branches and leaves, dark currents dance.

If one day you ask where the path has been, do not forget that first debate, my friend. :::align{right} ——Twelve Hexar ::::

Problem Description

Given an undirected connected graph with $n$ nodes and $n$ edges, it is guaranteed that there are no multiple edges and no self-loops (that is, the graph is a unicyclic tree, i.e., a tree with exactly one cycle). The weight of the edge connecting $u_i$ and $v_i$ is $w_i$.

You may perform several operations on the graph. In each operation, you choose one edge and send it a command $k=1$. You can start the next operation only after the previous operation ends (see the meaning below).

When an edge receives a command $k$, there are two possible cases:

1. This edge has not executed any command in the current operation: at the moment it receives the command, it increases its weight by $k$, and then at the next moment it sends a command $-k$ to all edges that share an endpoint with it.
2. This edge has already executed a command in the current operation: it ignores this command.

In particular:

1. The time taken for increasing weights, sending commands, and the transmission time from sending to receiving commands are all ignored.
2. If an edge receives multiple commands at the same moment, then it ignores all commands received at that moment, and the edge is considered to have executed a command in the current operation.
3. If there is no edge that is currently sending commands, or will send commands at the next moment, then the operation is considered to end. It can be proved that any operation must end.

After performing some operations, determine whether the sum of edge weights has a minimum value. If it does, output Yes and the minimum value. Otherwise output No, and instead output the minimum number of operations needed to make the sum of edge weights negative.

Input Format

The first line contains a positive integer $n$, the number of nodes and edges.

The next $n$ lines each contain three positive integers $u, v, w$.

Output Format

Output one line: Yes or No followed by a positive integer, representing the answer.

4
1 2 2
2 3 3
3 4 4
4 1 2

No 12

4
1 2 3
1 3 2
3 4 3
1 4 4

No 7

5
1 2 3
2 3 4
3 4 5
4 5 6
5 1 2

Yes 20

5
1 2 2
1 3 2
2 4 3
2 5 3
2 3 4

No 5

10
1 4 5
5 1 4
9 1 5
9 8 8
6 1 8
7 3 5
2 3 1
5 2 10
10 2 4
6 2 1

No 52

10
1 2 2
1 3 2
2 4 3
2 5 3
2 3 4
2 6 3
6 7 4
7 8 3
1 9 4
3 10 5

No 7

Hint

Sample 1 Explanation

Note that no matter how you operate, in each operation the total edge weight must decrease by $1$. The edge weights in the figure represent the received commands, and ##1## indicates operating on that edge.

Sample 2 Explanation

Repeating this operation $7$ times is enough.

Sample 3 Explanation

Note that no matter how you operate, the sum of edge weights only increases and never decreases, so the initial sum of edge weights is the minimum.

Constraints

This problem uses bundled testdata.

For all testdata, it is guaranteed that:

$1 \le u,v \le n \le 10^5$, $1 \le w \le 10^9$, $l\ge3$, where $l$ is the cycle length of the input unicyclic tree.

Translated by ChatGPT 5