题目背景

Description

Given a connected undirected graph, tell if its minimum spanning tree is unique.

Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V', E'), with the following properties:

1. V' = V.
2. T is connected and acyclic.

Definition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G = (V, E). The minimum spanning tree T = (V, E') of G is the spanning tree that has the smallest total cost. The total cost of T means the sum of the weights on all the edges in E'. Input

The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them. Output

For each input, if the MST is unique, print the total cost of it, or otherwise print the string 'Not Unique!'.

题目描述

给定一个连接的无向图，判断其最小生成树是否是唯一的。

定义 1（生成树）：考虑一个连通的无向图 G = （V， E）。G 的生成树是 G 的子图，例如 T = （V'， E'），具有以下性质：

1. V' = V. 2.T 是连接的和非循环的。

定义 2（最小生成树）：考虑一个边加权、连接、无向图 G = （V， E）。G 的最小生成树 T = （V， E'） 是总成本最小的生成树。T 的总成本是指 E' 中所有边的权重之和。

输入格式

第一行包含一个整数 t （1 <= t <= 20），即测试用例的数量。每个案例都代表一个图表。它以包含两个整数 n 和 m （1 <= n <= 100） 的线开始，即节点和边的数量。以下每条 m 线都包含一个三元组（习、yi、wi），表示 习 和 yi 由权重 = wi 的边连接。对于任意两个节点，最多有一个边连接它们。

输出格式

对于每个输入，如果 MST 是唯一的，请打印其总成本，或以其他方式打印字符串“Not Unique！”。

输入输出样例 #1

输入 #1

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

输出 #1

3
Not Unique!

说明/提示

翻译可能有问题，为机翻

提示：次最小生成树