大致思路见题解。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 200010, M = N << 1;

int n;
int p, q;
int h[N], e[M], ne[M], idx;
int dis[2][N], path[N], pcnt;
bool flg, st[N];

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs(int rt, int type)
{
	queue<int> q;
	q.push(rt);
	memset(dis[type], 0x3f, sizeof dis[type]);
	dis[type][rt] = 0;
	while (q.size())
	{
		int t = q.front(); q.pop();
		for (int i = h[t]; ~i; i = ne[i])
		{
			int j = e[i];
			if (dis[type][j] > dis[type][t] + 1)
			{
				dis[type][j] = dis[type][t] + 1;
				q.push(j);
			}
		}
	}
	
	int t = rt;
	for (int i = 1; i <= n; i ++ )
		if (dis[type][t] < dis[type][i]) t = i;
	
	return t;
}

void dfs(int u, int fa)
{
	if (u == q) 
	{
		flg = 1, path[ ++ pcnt] = u;
		return;
	}
	
	for (int i = h[u]; ~i; i = ne[i])
	{
		if (flg) break;
		int j = e[i];
		if (j == fa) continue;
		dfs(j, u);
	}
	
	if (flg) path[ ++ pcnt] = u;
}

signed main()
{
	memset(h, -1, sizeof h);
	cin >> n;
	for (int i = 1; i < n; i ++ )
	{
		int a, b;
		cin >> a >> b;
		add(a, b), add(b, a);
	}
	
	p = bfs(1, 0), q = bfs(p, 0);
	bfs(q, 1);
	dfs(p, -1);
	for (int i = 1; i <= pcnt; i ++ ) st[path[i]] = true;
	int res = 0, cnt = 0;
	for (int i = 1; i <= n; i ++ )
	{
		if (st[i]) continue;
		cnt ++ ;
		res += max(dis[0][i], dis[1][i]); 
	}
	cnt = n - cnt - 1;
	res += (1 + cnt) * cnt / 2;
	
	cout << res << '\n';
	for (int i = 1; i <= n; i ++ )
	{
		if (st[i]) continue;
		if (dis[0][i] > dis[1][i]) cout << p << ' ' << i << ' ' << i << '\n';
		else cout << q << ' ' << i << ' ' << i << '\n';
	}
	for (int i = 1; i < pcnt; i ++ )
		cout << p << ' ' << path[i] << ' ' << path[i] << '\n';
	
	return 0;
}