{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Given a connected undirected graph, tell if its minimum spanning tree is unique.\r\u003cbr\u003e\r\u003cbr\u003eDefinition 1 (Spanning Tree): Consider a connected, undirected graph G \u003d (V, E). A spanning tree of G is a subgraph of G, say T \u003d (V\u0027, E\u0027), with the following properties:\r\u003cbr\u003e1. V\u0027 \u003d V.\r\u003cbr\u003e2. T is connected and acyclic.\r\u003cbr\u003e\r\u003cbr\u003eDefinition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G \u003d (V, E). The minimum spanning tree T \u003d (V, E\u0027) 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\u0027.\r\u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains a single integer t (1 \u0026lt;\u003d t \u0026lt;\u003d 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 \u0026lt;\u003d n \u0026lt;\u003d 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 \u003d wi. For any two nodes, there is at most one edge connecting them."}},{"title":"Output","value":{"format":"HTML","content":"For each input, if the MST is unique, print the total cost of it, or otherwise print the string \u0027Not Unique!\u0027."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3 3\r\n1 2 1\r\n2 3 2\r\n3 1 3\r\n4 4\r\n1 2 2\r\n2 3 2\r\n3 4 2\r\n4 1 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\nNot Unique!\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}