stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <bitset>

#include <algorithm>

#include <cmath>



using namespace std;



int main(void) {

    int H, W;

    cin >> H >> W;

    vector< vector<int> > grid(H+2, vector<int>(W+2));

    for(int i=1; i<=H; i++) {

        for(int j=1; j<=W; j++) {

            int A;

            cin >> A;

            grid[i][j] += A;

        }

    }

    for(int i=1; i<=H; i++) {

        for(int j=1; j<=W; j++) {

            int B;

            cin >> B;

            grid[i][j] -= B;

        }

    }



    vector< vector< bitset<100'000> > > dp(H+2, vector< bitset<100'000> >(W+2));

    dp[1][1].set(50'000 + grid[1][1]);

    dp[1][1].set(50'000 - grid[1][1]);

    for(int i=1; i<=H; i++) {

        for(int j=1; j<=W; j++) {

            for(int k=100; k<=99'900; k++) {

                if(dp[i][j][k]) {

                    dp[i+1][j].set(k + grid[i+1][j]);

                    dp[i+1][j].set(k - grid[i+1][j]);

                    dp[i][j+1].set(k + grid[i][j+1]);

                    dp[i][j+1].set(k - grid[i][j+1]);

                }

            }

        }

    }



    int ans = numeric_limits<int>::max();

    for(int k=100; k<=99'900; k++) {

        if(dp[H][W][k]) {

            ans = min(ans, abs(50'000 - k));

        }

    }



    cout << ans << endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.8085023911824174x):
#include <iostream>

#include <vector>

#include <bitset>

#include <algorithm>

#include <cmath>



using namespace std;



int main(void) {

    int H, W;

    cin >> H >> W;

    vector< vector<int> > grid(H+2, vector<int>(W+2));

    for(int i=1; i<=H; i++) {

        for(int j=1; j<=W; j++) {

            int A;

            cin >> A;

            grid[i][j] += A;

        }

    }

    for(int i=1; i<=H; i++) {

        for(int j=1; j<=W; j++) {

            int B;

            cin >> B;

            grid[i][j] -= B;

        }

    }



    vector< vector< bitset<20'000> > > dp(H+2, vector< bitset<20'000> >(W+2));

    dp[1][1].set(10'000 + grid[1][1]);

    dp[1][1].set(10'000 - grid[1][1]);

    for(int i=1; i<=H; i++) {

        for(int j=1; j<=W; j++) {

            for(int k=100; k<=19'900; k++) {

                if(dp[i][j][k]) {

                    dp[i+1][j].set(k + grid[i+1][j]);

                    dp[i+1][j].set(k - grid[i+1][j]);

                    dp[i][j+1].set(k + grid[i][j+1]);

                    dp[i][j+1].set(k - grid[i][j+1]);

                }

            }

        }

    }



    int ans = numeric_limits<int>::max();

    for(int k=100; k<=19'900; k++) {

        if(dp[H][W][k]) {

            ans = min(ans, abs(10'000 - k));

        }

    }



    cout << ans << endl;

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



int h, w;

int a[80][80];

bool dp[80][80][2 * 80 * 80 + 1];



int solve() {

  const int kmax = 2 * 80 * 80;

  for (int i = 0; i < h; ++i) {

    for (int j = 0; j < w; ++j) {

      int diff = a[i][j];

      if (i == 0 && j == 0) {

        dp[i][j][diff] = true;

      } else {

        for (int k = 0; k <= kmax; ++k) {

          for (int type : { 1, -1 }) {

            int pk = k + type * diff;

            if (pk < 0) pk = -pk;

            if (pk > kmax) continue;

            bool u = i == 0 ? false : dp[i - 1][j][pk];

            bool l = j == 0 ? false : dp[i][j - 1][pk];

            if (!u && !l) continue;

            dp[i][j][k] = true;

          }

        }

      }

    }

  }

  

  for (int k = 0; k <= kmax; ++k) {

    if (dp[h - 1][w - 1][k]) return k;

  }

  return 1e9;

}



void input() {

  cin >> h >> w;

  int tmp[80][80];

  for (int i = 0; i < h; ++i) {

    for (int j = 0; j < w; ++j) {

      cin >> tmp[i][j];

    }

  }

  for (int i = 0; i < h; ++i) {

    for (int j = 0; j < w; ++j) {

      int buf;

      cin >> buf;

      a[i][j] = abs(buf - tmp[i][j]);

    }

  }

}



int main() {

  input();

  cout << solve() << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.1140972785847043x):
#include <bits/stdc++.h>

using namespace std;



using Bits = bitset<4 * 80 * 80 + 1>;

int h, w;

int a[80][80];

Bits dp[80][80];



int solve() {

  const int kmax = 2 * 80 * 80;

  for (int i = 0; i < h; ++i) {

    for (int j = 0; j < w; ++j) {

      int diff = a[i][j];

      if (i == 0 && j == 0) {

        dp[i][j][kmax + diff] = true;

        dp[i][j][kmax - diff] = true;

      } else {

        Bits sum;

        if (i > 0) {

          sum |= dp[i - 1][j] << diff;

          sum |= dp[i - 1][j] >> diff;

        }

        if (j > 0) {

          sum |= dp[i][j - 1] << diff;

          sum |= dp[i][j - 1] >> diff;

        }

        dp[i][j] = sum;

      }

    }

  }

  

  for (int k = 0; k <= kmax; ++k) {

    if (dp[h - 1][w - 1][kmax + k]) return k;

    if (dp[h - 1][w - 1][kmax - k]) return k;

  }

  return 1e9;

}



void input() {

  cin >> h >> w;

  int tmp[80][80];

  for (int i = 0; i < h; ++i) {

    for (int j = 0; j < w; ++j) {

      cin >> tmp[i][j];

    }

  }

  for (int i = 0; i < h; ++i) {

    for (int j = 0; j < w; ++j) {

      int buf;

      cin >> buf;

      a[i][j] = abs(buf - tmp[i][j]);

    }

  }

}



int main() {

  input();

  cout << solve() << endl;

}
// Slower C++ solution:
#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

#include<map>

#include<queue>

#define Max 9

int gg[Max]={1,2,3,4,5,6,7,8,0}, s[Max];



int ff[4][2] = {0,-1,1,0,0,1,-1,0};

int sum;

struct node

{

	int a[Max];

	int step;

};

map<int ,int >m;





int bfs()

{

	node tt;

	memcpy(tt.a,s,sizeof(s));

	tt.step = 0;

	queue<node > q;

	q.push(tt);

	while(!q.empty())

	{

		node star = q.front();

		q.pop();

		int i;

		for(i = 0;i<9;i++)

			if(star.a[i]==0)

				break;

		int y = i/3;

		int x = i%3;

		for(i = 0;i<4;i++)

		{

			int tx = x + ff[i][0];

			int ty = y + ff[i][1];

			if(tx >= 0&&ty>=0&&ty<3&&tx<3)

			{

				node end;

				memcpy(end.a,star.a,sizeof(star.a));

				int k = ty*3+tx;

				swap(end.a[k],end.a[y*3+x]);

				int sum1 = 0;

				for(int j = 0;j<9;j++)

					sum1 = sum1*10+end.a[j];

				if(!m[sum1])

				{

					m[sum1] = sum++;

					end.step = star.step+1;

					if(memcmp(end.a,gg,sizeof(gg))==0)

						return end.step;

					q.push(end);

				}

			}

		}

	}

}

int main()

{

	int i,j;



	while(~scanf("%d",&s[0]))

	{

		m.clear();

		int k = s[0];

		sum = 1;

		for(i = 1;i<9;i++)

		{

			scanf("%d",&s[i]);

			k = k*10+s[i];

		}

		m[k] = sum++;

		if(memcmp(s,gg,sizeof(gg))==0)

			printf("0\n");

		else printf("%d\n",bfs());

		

	}	

	return 0;

} 


// Faster C++ solution for the same problem (measured speedup: 1.1097614610900708x):
#include<cstdio>

#include<cstring>

#include<queue>

#include<map>

#include<algorithm>

using namespace std;

const int maxn = 10;



typedef struct Node{

	int a[maxn];

	int step;

}Node;



int arr[maxn],start[maxn];//start arr 分别是开始和目标状态 

int cnt;//记录map的值 

int dx[4] = {0,0,-1,1};

int dy[4] = {-1,1,0,0};

map<int,int>mp;



int bfs(){

	queue<Node>que;

	Node node;

	memcpy(node.a,start,sizeof(start));

	node.step = 0;

	que.push(node);

	while(!que.empty()){

		//for()...

		node = que.front();

		que.pop();

		int index;

		for(int i = 0; i<9; i++){

			if(node.a[i] == 0) index = i;

		}

		int r = index/3;

		int c = index%3;

		for(int i = 0; i<4; i++){

			int nr = r + dx[i];

			int nc = c + dy[i];

			if(0<=nr && nr<3 && 0<=nc && nc<3){

				Node node_new;

				int index_new = nr*3 + nc;

				int sum = 0;

				memcpy(node_new.a,node.a,sizeof(node.a));				

				swap(node_new.a[index],node_new.a[index_new]);

				for(int j = 0; j<9; j++){

					sum = sum*10 + node_new.a[j];

				}

				if(mp[sum] == 0){

					mp[sum] = cnt++;

					node_new.step = node.step+1;

					if(memcmp(arr,node_new.a,sizeof(arr)) == 0){

						return node_new.step;

					}

					que.push(node_new);

				}

			}

		}

		//if !vis[i] ...que.push

	}

}

int main()

{

	int sum1 = 0, cnt = 0, sum = 0;

	for(int i = 1; i<=8; i++){

		sum1 = sum1*10 + i;

		start[i-1] = i; 

	}

	sum1 = sum1*10;

	start[8] = 0;

	mp[sum1] = cnt++;

	for(int i = 0; i<9; i++){

		scanf("%d",&arr[i]);

		sum = sum*10 + arr[i];

	}

	if(sum == sum1) printf("0\n");

	else{

		printf("%d\n",bfs());

	}

	

	return 0;

}
// Slower C++ solution:
#include<stdio.h>

#include<algorithm>

#include<iostream>

using namespace  std;

int fa[100010];

int n,m;

struct edge{

	int x,y,w;

	edge(int x=0,int y=0 ,int w=0 ):x(x),y(y),w(w){

	}

}a[100010];

int getfa(int x){

	if(x==fa[x]) return x;

	else return getfa(fa[x]);

}

bool cmp(edge a,edge b){

	return a.w<b.w;

}

int f(){

	int ans=0;

	sort(a,a+m,cmp);

	int cnt=n;

	for(int i=0;i<n;i++) fa[i]=i;

	for(int i=0;i<m;i++){

		int f1=getfa(a[i].x),

		f2=getfa(a[i].y);

		if(f1!=f2){

			ans+=a[i].w;

			cnt--;

			fa[f1]=f2;

			if(cnt==1) break;

		}

	}

	return ans;

}

int main(){

	scanf("%d%d",&n,&m);

	for(int i=0;i<m;i++){

		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);

	}

	printf("%d\n",f());

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.212246706212316x):
#include <iostream>

#include <stdio.h>

#include <vector>

#include <algorithm>

#define  MAXN 10010

using namespace std;

struct Edge

{

	int point1;

	int point2;

	int weight;

};

bool cmp(Edge &x, Edge &y)

{

	return x.weight < y.weight;

}

int pre[MAXN];

vector <Edge> vec;

int find(int x)

{//并查集

	int root = x;



	while (pre[root] != root)

		root = pre[root];//找根

	int t = x;

	while (pre[t] != root)

	{//路径压缩

		int temp = pre[t];

		pre[t] = root;

		t = temp;

	}



	return root;

}

int main()

{

	int n, m;

	int min_sum = 0;



	scanf("%d%d", &n, &m);//n是点数，m是边数

	for (int i = 0; i < n; i++)

		pre[i] = i;//初始化并查集

	for (int i = 0; i < m; i++)

	{//输入每条边的两个顶点及其权重

		Edge temp;



		scanf("%d%d%d", &temp.point1, &temp.point2, &temp.weight);

		vec.push_back(temp);

	}

	sort(vec.begin(), vec.end(), cmp);//按权重对边进行排序

	int coun = 0;

	for (int i = 0; i < m; i++)

	{//最多只有m条边

		int fx = find(vec[i].point1);

		int fy = find(vec[i].point2);



		if (fx != fy)

		{//如果这条边的两个顶点所在集合不相同就合并

			coun++;//成功合并后就多了一条边

			min_sum += vec[i].weight;

			pre[fx] = fy;//合并

			if (coun == n - 1)

				break;//krusal有n-1条边

		}

	}

	printf("%d\n", min_sum);

	return 0;

}
// Slower C++ solution:
#include<stdio.h>

#include<algorithm>

#include<iostream>

using namespace  std;

int fa[100010];

int n,m;

struct edge{

	int x,y,w;

	edge(int x=0,int y=0 ,int w=0 ):x(x),y(y),w(w){

	}

}a[100010];

int getfa(int x){

	if(x==fa[x]) return x;

	else return getfa(fa[x]);

}

bool cmp(edge a,edge b){

	return a.w<b.w;

}

int f(){

	int ans=0;

	sort(a,a+m,cmp);

	int cnt=n;

	for(int i=0;i<n;i++) fa[i]=i;

	for(int i=0;i<m;i++){

		int f1=getfa(a[i].x),

		f2=getfa(a[i].y);

		if(f1!=f2){

			ans+=a[i].w;

			cnt--;

			fa[f1]=f2;

			if(cnt==1) break;

		}

	}

	return ans;

}

int main(){

	scanf("%d%d",&n,&m);

	for(int i=0;i<m;i++){

		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);

	}

	printf("%d\n",f());

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.185871812202256x):
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

int n,m;

int fa[maxn],ran[maxn];

struct Edge{

	int l,r,w;

}pp[maxn];

bool cmp(const Edge &a,const Edge &b)

{

	return a.w<b.w;

}

void init(int size)

{

	for(int i=0;i<=size;i++)

		fa[i]=i,ran[i]=0;

}

int Find(int x)

{

	return fa[x]==x?x:Find(fa[x]);

}

void Union(int x,int y)

{

	int fx=Find(x),fy=Find(y);

	if(ran[x]>=ran[y]){

		ran[fx]+=ran[fy];

		fa[fy]=fx;

	}

	else {

		ran[fy]+=ran[fx];

		fa[fx]=fy;

	}

}

int main()

{

	int cnt=0,ans=0;

	cin>>n>>m;

	init(n);

	for(int i=1;i<=m;i++)

	{

		cin>>pp[i].l>>pp[i].r>>pp[i].w;

	}

	sort(pp+1,pp+1+m,cmp);

	for(int i=1;i<=m;i++)

	{

		if(Find(pp[i].l)!=Find(pp[i].r)){

			Union(pp[i].l,pp[i].r);

			ans+=pp[i].w;

		}

		if(cnt==n-1)break;

	}

	cout<<ans<<endl;

	return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

#define pb        emplace_back

#define fi        first

#define se        second

#define outl(x)   cout << (x) << '\n'

#define rep(i,n)     for(int i=0; i<(n); ++i)

typedef pair<int,int> pii;



int V, E;

vector<pii> G[100010];



int prim()

{

    vector<bool> used(V+1, false);

    priority_queue< pii, vector<pii>, greater<pii> > pq;

    int sum = 0;

    pq.emplace(pii(0,0));



    while ( !pq.empty() ) {

        const auto now = pq.top(); pq.pop();

        if (used[now.se]) continue;



        sum += now.fi;

        used[now.se] = true;

        for (const auto &e : G[now.se]) {

            pq.emplace(e);

        }

    }

    return sum;

}



signed main()

{

    cin.tie(0), ios::sync_with_stdio(false);



    cin >> V >> E;

    rep(i, E) {

        int s, t, w;

        cin >> s >> t >> w;

        G[s].pb(pii(w, t));

        G[t].pb(pii(w, s));

    }



    outl(prim());

}






// Faster C++ solution for the same problem (measured speedup: 3.491458974808264x):
#include "bits/stdc++.h"

using namespace std;

using i64 = long long;

using pii = pair<i64, i64>;

template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}

template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}

constexpr int INF  = 0x3f3f3f3f;

constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;





struct Edge { // {{{

    int src, to;

    i64 cost;

    Edge(int src,  int to, i64 cost) : src(src), to(to), cost(cost) {}

    Edge(int to, i64 cost = 0) : Edge(-1, to, cost) {}

    Edge() {}

    bool operator< (const Edge &o) const { return cost < o.cost; }

    bool operator> (const Edge &o) const { return cost > o.cost; }

};

using Edges = vector<Edge>;

using WGraph = vector<vector<Edge>>;

using UGraph = vector<vector<int>>;

// }}}







struct UnionFind {

    vector<int> u;

    explicit UnionFind(int n): u(n+5, -1) {}

    int  size(int i)        { return (-u[root(i)]); }

    int  root(int x)        { return (u[x] < 0)? x : u[x] = root(u[x]); }

    bool same(int x, int y) { return root(x) == root(y); }

    bool unite(int x, int y){ return (x=root(x)) == (y=root(y))? false : (u[x]+=u[y], u[y]=x, true); }

};



i64 kruskal(Edges &es, int V)

{

    UnionFind uf(V);

    i64 costSum = 0;



    sort(es.begin(), es.end());

    for (const auto &e : es) {

        if (uf.unite(e.src, e.to)) costSum += e.cost;

    }



    return costSum;

}



void AOJ_GRL_2_A()

{

    int V, E;

    cin >> V >> E;



    Edges es(E);

    for (int i = 0; i < E; ++i) {

        int s, t, w;

        cin >> s >> t >> w;

        es[i] = Edge(s, t, w);

    }



    cout << kruskal(es, V) << endl;



}



signed main()

{

    ios::sync_with_stdio(false); cin.tie(nullptr);



    AOJ_GRL_2_A();



    return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<vector>

#include<queue>

#include<algorithm>

using namespace std;



//Prim

struct edge{int to,cost;};



int main(){

  int V,E;

  vector<edge> G[10000];

  scanf("%d %d",&V,&E);

  for(int i=0;i<E;i++){

    int s,t,w;

    scanf("%d %d %d",&s,&t,&w);

    edge tmp;

    tmp.cost = w;

    tmp.to = t;

    G[s].push_back(tmp);

    tmp.to = s;

    G[t].push_back(tmp);

  }

  int ans = 0;

  bool used[V];

  fill(used,used+V,false);

  priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;

  q.push(make_pair(0,0));

  while(!q.empty()){

    pair<int,int> p = q.top();

    q.pop();

    int c = p.first;

    int v = p.second;

    if(used[v]) continue;

    used[v] = true;

    ans+=c;

    for(int i=0;i<G[v].size();i++){

      q.push(make_pair(G[v][i].cost,G[v][i].to));

    }

  }

  printf("%d\n",ans);

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.276071009732609x):
#include<cstdio>

#include<vector>

#include<queue>

#include<algorithm>

using namespace std;



struct union_find{

  int par[10000],rank[10000];

  union_find(int n){

    for(int i=0;i<n;i++){

      par[i] = i;

      rank[i] = 1;

    }

  }

  int find(int x){

    if(par[x]==x) return x;

    else return par[x] = find(par[x]);

  }

  void unite(int x,int y){

    x = find(x);

    y = find(y);

    if(x==y) return;

    if(rank[x]>rank[y]) par[y] = x;

    else{

      if(rank[x]==rank[y]) rank[y]+=rank[x];

      par[x] = y;

    }

  }

  bool same(int x,int y){return find(x)==find(y);}

};



int main(){

  int v,e;

  scanf("%d %d",&v,&e);

  union_find uf(v);

  vector<pair<int,pair<int,int> > > E;

  for(int i=0;i<e;i++){

    int s,t,w;

    scanf("%d %d %d",&s,&t,&w);

    E.push_back(make_pair(w,make_pair(s,t)));

  }

  sort(E.begin(),E.end());

  int ans = 0;

  //bool used[v];

  //fill(used,used+v,false);

  for(int i=0;i<E.size();i++){

    int s = E[i].second.first;

    int t = E[i].second.second;

    int w = E[i].first;

    if(!uf.same(s,t)){

      ans+=w;

      uf.unite(s,t);

    }

  }

  printf("%d\n",ans);

  return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<vector>

#include<queue>

#include<algorithm>

using namespace std;



//Prim

struct edge{int to,cost;};



int main(){

  int V,E;

  vector<edge> G[10000];

  scanf("%d %d",&V,&E);

  for(int i=0;i<E;i++){

    int s,t,w;

    scanf("%d %d %d",&s,&t,&w);

    edge tmp;

    tmp.cost = w;

    tmp.to = t;

    G[s].push_back(tmp);

    tmp.to = s;

    G[t].push_back(tmp);

  }

  int ans = 0;

  bool used[V];

  fill(used,used+V,false);

  priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;

  q.push(make_pair(0,0));

  while(!q.empty()){

    pair<int,int> p = q.top();

    q.pop();

    int c = p.first;

    int v = p.second;

    if(used[v]) continue;

    used[v] = true;

    ans+=c;

    for(int i=0;i<G[v].size();i++){

      q.push(make_pair(G[v][i].cost,G[v][i].to));

    }

  }

  printf("%d\n",ans);

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2761103099801585x):
#include<cstdio>

#include<algorithm>

#include<vector>

#include<queue>

using namespace std;



typedef pair<int,int> pii;

const int INF =  1000000000;



int par[10000],rnk[10000];



void init(int n){

  for(int i=0;i<n;i++){

    par[i] = i;

    rnk[i] = 1;

  }

}

int find(int x){

  if(par[x]==x) return x;

  else return par[x] = find(par[x]);

}

bool same(int x,int y){

  return find(x)==find(y);

}

void unite(int x,int y){

  x = find(x);

  y = find(y);

  if(rnk[x]>rnk[y]) par[y] = x;

  else{

    par[x] = y;

    if(rnk[x]==rnk[y]) rnk[y]++;

  }

  return;

}



int main(){

  int V,E;

  vector<pair<int,pii> > es;

  scanf("%d %d",&V,&E);

  for(int i=0;i<E;i++){

    int s,t,w;

    scanf("%d %d %d",&s,&t,&w);

    es.push_back(make_pair(w,pii(s,t)));

  }

  int ans = 0;

  int cost[10000];

  fill(cost,cost+V,INF);

  sort(es.begin(),es.end());

  cost[0] = 0;

  init(V);

  for(int i=0;i<es.size();i++){

    if(!same(es[i].second.first,es[i].second.second)){

      ans += es[i].first;

      unite(es[i].second.first,es[i].second.second);

    }

  }

  printf("%d\n",ans);

  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <string>

#include <queue>

#include <vector>

#include <algorithm>

#include <utility>



#define INF 1000000000



using namespace std;



typedef long long int lli;

typedef pair<int, int> P;



struct edge{

	int to, cost;

};



int V, E;

vector<edge> e[10000];

priority_queue< P, vector<P>, greater<P> > que;

bool used[10000];





int main(void){

	cin >> V >> E;



	for(int i = 0;i < V;i++){

		used[i] = false;

	}



	for(int i = 0;i < E;i++){

		int a, b, c;

		cin >> a >> b >> c;

		edge d;

		d.to = b;

		d.cost = c;

		e[a].push_back(d);

		d.to = a;

		e[b].push_back(d);

	}





	que.push(P(0, 0));

	long long int res = 0;



	while(!que.empty()){



		P a = que.top();

		que.pop();

		if(used[a.second]) continue;

		used[a.second] = true;

		res += a.first;



		for(int u = 0;u < e[a.second].size();u++){

			if(!used[e[a.second][u].to])

				que.push(P(e[a.second][u].cost, e[a.second][u].to));

		}

	}

	cout << res << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.2446187154779167x):
#include <iostream>

#include <iomanip>

#include <string>

#include <vector>

#include <queue>

#include <algorithm>

#include <utility>

#include <cmath>



#define INF_LL 9000000000000000000

#define INF 2000000000



#define REP(i, n) for(int i = 0;i < (n);i++)

#define FOR(i, a, b) for(int i = (a);i < (b);i++)



using namespace std;



typedef long long ll;

typedef pair<int, int> PII;



class Union_find{

private:

	vector<int> par;

	vector<int> rank;

	int n;



public:

	Union_find(int a){

		n = a;

		for(int i = 0;i < n;i++){

			par.push_back(i);

			rank.push_back(0);

		}

	}



	int find(int x){

		if(par[x] == x){

			return x;

		}else{

			return par[x] = find(par[x]);

		}

	}



	void unite(int x, int y){

		x = find(x);

		y = find(y);

		if(x == y) return;



		if(rank[x] < rank[y]){

			par[x] = y;

		}else{

			par[y] = x;

			if(rank[x] == rank[y]) rank[x]++;

		}

	}



	bool same(int x, int y){

		return find(x) == find(y);

	}

};



struct edge{ int u, v, cost; };



edge es[100000];

int V, E;



bool comp(const edge& e1, const edge& e2){

	return e1.cost < e2.cost;

}



int main(void){

	cin >> V >> E;

	for(int i = 0;i < E;i++){

		int a, b, c;

		cin >> a >> b >> c;

		es[i].u = a;

		es[i].v = b;

		es[i].cost = c;

	}

	Union_find uf(V);

	sort(es, es+E, comp);

	int res = 0;

	for(int i = 0;i < E;i++){

		edge e = es[i];

		if(!uf.same(e.u, e.v)){

			uf.unite(e.u, e.v);

			res += e.cost;

		}

	}

	cout << res << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define INF 1000000000

#define MAX_V 10000

#define MAX_E 100000

using namespace std;

typedef pair<int, int> P;

struct edge {

	int to, cost;

	edge(int to_, int cost_) : to(to_), cost(cost_) {}

};



int V, E;

vector<edge> G[MAX_V];



int Prim() {

	int res = 0;

	bool used[MAX_V];

	priority_queue<P, vector<P>, greater<P>> que;

	for (int i = 0; i < V; i++) {

		used[i] = false;

	}

	que.push(P(0, 0));

	while (!que.empty()) {

		P p = que.top(); que.pop();

		int v = p.second;

		if (used[v]) continue;

		used[v] = true;

		res += p.first;

		for (int i = 0; i < G[v].size(); i++) {

			edge e = G[v][i];

			que.push(P(e.cost, e.to));

		}

	}

	return res;

}



int main()

{

	cin >> V >> E;

	for (int i = 0, s, t, c; i < E; i++) {

		cin >> s >> t >> c;

		G[s].push_back(edge(t, c));

		G[t].push_back(edge(s, c));

	}

	cout << Prim() << endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.256991223108436x):
#include <bits/stdc++.h>

#define INF 1000000000

#define MAX_V 10000

#define MAX_E 100000

using namespace std;

typedef pair<int, int> P;

struct edge { int u, v, cost; };



bool comp(const edge& e1, const edge& e2){

	return e1.cost < e2.cost;

}



int V, E;

edge es[MAX_E];



class UnionFind {

	vector<int> data;

	int root(int a) {

		return data[a] < 0 ? a : data[a] = root(data[a]);

	}

public:

	UnionFind(int n) : data(n, -1) {}

	bool Find(int a, int b) {

		return root(a) == root(b);

	}

	void Union(int a, int b) {

		int ra = root(a), rb = root(b);

		if (ra == rb) return;

		if (data[ra] < data[rb]) {

			data[ra] += data[rb];

			data[rb] = a;

		}

		else {

			data[rb] += data[ra];

			data[ra] = b;

		}

	}

};



int Kruskal() {

	int res = 0;

	UnionFind uf(V);

	sort(es, es + E, comp);

	for (int i = 0; i < E; i++) {

		edge e = es[i];

		if (!uf.Find(e.u, e.v)) {

			uf.Union(e.u, e.v);

			res += e.cost;

		}

	}

	return res;

}



int main()

{

	cin >> V >> E;

	for (int i = 0; i < E; i++) {

		cin >> es[i].u >> es[i].v >> es[i].cost;

	}

	cout << Kruskal() << endl;

	return 0;

}