题目链接：这里
题意：构造一个n个点，m条有向边的图，需要满足两个要求：
1.任意一对点对之间最多有一条有向边，且没有自环。
2.保证图联通，m条边的边权严格属于[1, m]且互不相同，从任意点出发，经过任意路径后回到起始点，经过的边权总和是3的倍数。
解法：构造好题，方法 对于每个点i < n构造出i~i+1权值为i的边，用n~1调整权值构造出环，然后其余权值为w的边在i~j且i~j权值与w对3同余的路径上添加。

//HDU 4781

#include <bits/stdc++.h>
using namespace std;
const int maxn = 6500;
int cnt[4]; //记录模3系权值的出现次数
int f[maxn][4]; //f[i][j]，权值为j,的边有哪些
int sum[maxn];
int main()
{
    int T, ks = 0, n, m;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        printf("Case #%d:\n", ++ks);
        memset(cnt, 0, sizeof(cnt));
        memset(f, 0, sizeof(f));
        //先n个点构成1个环
        for(int i = 1; i < n; i++){
            printf("%d %d %d\n", i, i + 1, i);
            sum[i + 1] = sum[i] + i;
        }
        for(int i = n; i <= m; i++){
            int x = i%3;
            f[++cnt[x]][x] = i;
        }
        int lastedge = (3 - (sum[n] - sum[1]) % 3) % 3;
        printf("%d 1 %d\n", n, f[cnt[lastedge]--][lastedge]);
        //构造剩下的n - m条边
        for(int i = 1; i <= n - 2; i++){
            for(int j = i + 2; j <= n; j++){
                if(i == 1 && j == n) continue;
                int curedge = (sum[j] - sum[i] + 3) % 3;
                if(cnt[curedge]){
                    printf("%d %d %d\n", i, j, f[cnt[curedge]--][curedge]);
                }
            }
        }
    }
    return 0;
}