1#include<bits/stdc++.h>
2#include<iostream>
3using namespace std;
4using ll = long long;
5
6struct edge {
7 int u;
8 int v;
9 int w;
10};
11const int maxN = 100001;
12const int INF = 1e9; // so vo cung
13
14int n, m; // n: so dinh, m: so canh
15int parent[maxN], sz[maxN];
16vector<edge> canh;
17
18void make_set() {
19 for(int i = 1; i <= n; i++) {
20 parent[i] = i;
21 sz[i] = 1;
22 }
23}
24
25int find (int v) {
26 if(v == parent[v]) {
27 return v;
28 }
29
30 return parent[v] = find(parent[v]);
31}
32
33bool Union(int a, int b) {
34 a = find(a);
35 b = find(b);
36 if(a == b) {
37 return false; // khong the gop a, b voi nhau
38 }
39 if(sz[a] < sz[b]) {
40 swap(a, b);
41 }
42 parent[b] = a;
43 sz[a] + sz[b];
44 return true;
45}
46
47void inp() {
48 cin >> n >> m;
49 for(int i=0; i<m; i++) {
50 int x, y, w;
51 cin >> x >> y >> w;
52 edge e;
53 e.u = x;
54 e.v = y;
55 e.w = w;
56 canh.push_back(e);
57 }
58}
59
60bool cmp(edge a, edge b) {
61 return a.w < b.w;
62}
63
64void kruskal() {
65 // Tao cay khung cuc tieu rong
66 vector<edge> mst;
67 int d = 0;
68
69 // Sort danh sach canh theo chieu dai tang dan
70 sort(canh.begin(), canh.end(), cmp);
71
72 // Lap qua cac canh
73 for(int i=0; i<m; i++) {
74 if(mst.size() == n-1) {
75 break;
76 }
77
78 edge e = canh[i]; // chon canh e la canh nho nhat
79 if(Union(e.u, e.v)) {
80 mst.push_back(e);
81 d += e.w;
82 }
83 }
84
85 // Tra ve ket qua
86 if(mst.size() != n-1) {
87 cout << "Do thi khong lien thong !\n"; // Do thi khong co cay khung
88 } else {
89 cout << "MST: " << d << endl;
90 for(auto it: mst) {
91 cout << it.u << " " << it.v << " " << it.w << endl;
92 }
93 }
94}
95
96int main() {
97 // Chuyen NHAP, XUAT thanh file
98 freopen("lab_6_input.INP", "r", stdin);
99 freopen("lab_6_output.OUT", "w", stdout);
100
101 // INPUT
102 inp();
103 make_set();
104
105 // OUTPUT
106 kruskal();
107}