a35b4979.cpp

#include <bits/stdc++.h>
#define alive std::cout << "$LINE @" << __LINE__ << " ALIVE" << std::endl
#define watch(var) std::cout << "$ LINE @" << __LINE__ << " FUN @" << __FUNCTION__ \
                             << " VAR @" << (#var) << ": " << (var) << std::endl

using namespace std;

typedef int i32;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
typedef double f64;
typedef long double f128;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    x = 0;
    bool neg = false;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

const int N = 1e5 + 5;
const int FIB[] = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025};

int n, m;

namespace UFS
{
    int fa[N];

    int find(int x)
    {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }
    inline void prepare()
    {
        for (int i = 1; i <= n; ++i)
        {
            fa[i] = i;
        }
    }
} // namespace UFS

struct Edge
{
    int u, v, w;
    inline bool operator<(const Edge &rhs) const
    {
        return w < rhs.w;
    }
} e[N];

inline int MST()
{
    UFS::prepare();

    int res = 0, edge = 0;
    for (int i = 1; i <= m; ++i)
    {
        int u = e[i].u, v = e[i].v;
        u = UFS::find(u), v = UFS::find(v);
        if (u != v)
        {
            UFS::fa[v] = u;
            res += e[i].w;
            ++edge;
        }
    }

    return edge == n - 1 ? res : -1;
}

inline void solve()
{
    read(n), read(m);
    for (int i = 1; i <= m; ++i)
    {
        read(e[i].u), read(e[i].v), read(e[i].w);
    }
    sort(e + 1, e + m + 1);
    int minimum = MST();
    if (minimum == -1)
    {
        puts("No");
        return;
    }
    reverse(e + 1, e + m + 1);
    int maximum = MST();
    if (maximum == -1)
    {
        puts("No");
        return;
    }
    for (const auto &x : FIB)
    {
        if (x >= minimum && x <= maximum)
        {
            puts("Yes");
            return;
        }
    }
    puts("No");
}

int main()
{
    int T;
    read(T);

    for (int cas = 1; cas <= T; ++cas)
    {
        printf("Case #%d: ", cas);
        solve();
    }

    return 0;
}