Archiepuls @ 2021-09-16 11:51:14
#include<bits/stdc++.h>
using namespace std;
int n, m;
long long sum = 0;
struct Edge
{
int to, w;
Edge(int t, int data)
{
to = t;
w = data;
}
};
int main()
{
cin >> n >> m;
vector<Edge> v[n + 1];
int visit[n + 1], dis[n + 1];
for(int i = 0; i <= n; i++)
{
visit[i] = 0;
dis[i] = INT_MAX;
}
for(int i = 1; i <= m; i++)
{
int in, to, w;
cin >> in >> to >> w;
v[in].push_back(Edge(to, w));
v[to].push_back(Edge(in, w));
}
int x = v[1].size();
for(int i = 0; i < x; i++)
{
dis[v[1][i].to] = v[1][i].w;
}
dis[1] = 0;
visit[1] = 1;
for(int i = 1; i < n; i++)
{
int smin = INT_MAX;
int x;
for(int j = 1; j <= n; j++)
{
if(!visit[j] && dis[j] < smin)
{
smin = dis[j];
x = j;
}
}
sum = (long long)(sum + dis[x]);
visit[x] = 1;
int l = v[x].size();
for(int k = 0; k < l; k++)
{
if(!visit[v[x][k].to] && v[x][k].w < dis[v[x][k].to])
{
dis[v[x][k].to] = v[x][k].w;
}
}
}
for(int i = 1; i <= n; i++)
if(!visit[i])
{
cout << "orz" << endl;
return 0;
}
cout << sum << endl;
return 0;
}