QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#233130#7177. Many Many CyclesikefumyTL 186ms5792kbC++205.6kb2023-10-31 13:48:142023-10-31 13:48:14

Judging History

你现在查看的是最新测评结果

  • [2023-10-31 13:48:14]
  • 评测
  • 测评结果:TL
  • 用时:186ms
  • 内存:5792kb
  • [2023-10-31 13:48:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ti3 tuple<int,int,int>
#define int128 __int128_t
#define pii128 pair<int128,int128>
const int inf = 1 << 30;
const ll linf = 1e18;
const ll mod = 1e9 + 7;
const db EPS = 1e-10;
const db pi = acos(-1);
template<class T> bool chmin(T& x, T y){
    if(x > y) {
        x = y;
        return true;
    } else return false;
}
template<class T> bool chmax(T& x, T y){
    if(x < y) {
        x = y;
        return true;
    } else return false;
}

// overload macro
#define CAT( A, B ) A ## B
#define SELECT( NAME, NUM ) CAT( NAME, NUM )

#define GET_COUNT( _1, _2, _3, _4, _5, _6 /* ad nauseam */, COUNT, ... ) COUNT
#define VA_SIZE( ... ) GET_COUNT( __VA_ARGS__, 6, 5, 4, 3, 2, 1 )

#define VA_SELECT( NAME, ... ) SELECT( NAME, VA_SIZE(__VA_ARGS__) )(__VA_ARGS__)

// rep(overload)
#define rep( ... ) VA_SELECT(rep, __VA_ARGS__)
#define rep2(i, n) for (int i = 0; i < int(n); i++)
#define rep3(i, a, b) for (int i = a; i < int(b); i++)
#define rep4(i, a, b, c) for (int i = a; i < int(b); i += c)

// repll(overload)
#define repll( ... ) VA_SELECT(repll, __VA_ARGS__)
#define repll2(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repll3(i, a, b) for (ll i = a; i < (ll)(b); i++)
#define repll4(i, a, b, c) for (ll i = a; i < (ll)(b); i += c)

// rrep(overload)
#define rrep( ... ) VA_SELECT(rrep, __VA_ARGS__)    
#define rrep2(i, n) for (int i = n - 1; i >= 0; i--)
#define rrep3(i, a, b) for (int i = b - 1; i >= a; i--)
#define rrep4(i, a, b, c) for (int i = b - 1; i >= a; i -= c)

// rrepll(overload)
#define rrepll( ... ) VA_SELECT(rrepll, __VA_ARGS__)
#define rrepll2(i, n) for (ll i = (ll)(n) - 1; i >= 0ll; i--)
#define rrepll3(i, a, b) for (ll i = b - 1; i >= (ll)(a); i--)
#define rrepll4(i, a, b, c) for (ll i = b - 1; i >= (ll)(a); i -= c)

// for_earh
#define fore(e, v) for (auto&& e : v)

// vector
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()


struct LCA{
    int N;
    int logn;
    vector<vector<int>> G;
    vector<vector<int>> par;
    vector<int> depth, used;

    LCA(int n) : N(n), logn(0), G(n + 1), depth(n + 1), used(n + 1) {
        while((1 << logn) <= N) logn++;
        par = vector<vector<int>>(logn, vector<int>(n + 1));
    }

    void add_edge(int u, int v){
        G[u].push_back(v);
        G[v].push_back(u);
    }

    void dfs(int v, int p, int d){
        par[0][v] = p;
        depth[v] = d;
        used[v] = true;

        for(auto& u : G[v]){
            if(p == u) continue;
            dfs(u, v, d + 1);
        }
    }

    void setting(){
        for (int i = 1; i <= N; i++) {
            if (used[i]) continue;
            dfs(i, -1, 0);
        }
        for(int i = 1; i < logn; i++){
            for(int j = 1; j <= N; j++){
                if(par[i - 1][j] < 0) par[i][j] = -1;
                else par[i][j] = par[i - 1][par[i - 1][j]];
            }
        }
    }

    int get_lca(int u, int v){
        if(depth[u] < depth[v]) swap(u, v);
        int d = depth[u] - depth[v];

        for(int i = 0; i < logn; i++){
            if(d >> i & 1) u = par[i][u];
        }
        if(u == v) return u;

        for(int i = logn - 1; i >= 0; i--){
            if(par[i][u] != par[i][v]){
                u = par[i][u];
                v = par[i][v];
            }
        }
        return par[0][u];
    }

    int get_len(int u, int v) {
        int cp = get_lca(u, v);
        return depth[u] + depth[v] - depth[cp] * 2;
    }
};

int N, M, par[5010];
ll depth[5010], g;
vector<pil> G[5010];
vector<pil> TG[5010];
vector<pil> rem[5010];
bool used[5010];
LCA lca(0);

void dfs(int v, ll d) {
    used[v] = true;
    depth[v] = d;
    for (auto& [u, w] : G[v]) {
        if (used[u]) {
            if (u != par[v]) {
                rem[v].emplace_back(u, w);
                rem[u].emplace_back(v, w);
            }
            continue;
        }

        par[u] = v;
        TG[v].emplace_back(u, w);
        TG[u].emplace_back(v, w);
        lca.add_edge(u, v);
        dfs(u, d + w);
    }
}

void make_ans(int v, int p) {
    used[v] = true;
    for (auto&& [u, w] : TG[v]) {
        if (u == p) continue;
        make_ans(u, v);
    }

    for (auto&& [u, w] : rem[v]) {
        if (depth[u] > depth[v]) continue;
        g = gcd(g, w + depth[v] - depth[u]);
        int p = v;
        while (true) {
            for (auto&& [q, r] : rem[p]) {
                if (depth[q] < depth[p]) continue;
                if (max(u, v) == max(p, q) && min(u, v) == min(p, q)) continue;
                ll len = w + r + depth[p] - depth[u];
                len += depth[v] + depth[q] - 2 * depth[lca.get_lca(v, q)];
                g = gcd(g, len);
            }

            if (p == u) break;

            p = par[p];

        }
    }
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    cin >> N >> M;
    lca = LCA(N);
    rep (i, M) {
        int a, b, c;
        cin >> a >> b >> c;
        G[a].emplace_back(b, c);
        G[b].emplace_back(a, c);
    }

    rep (i, 1, N + 1) {
        if (used[i]) continue;
        dfs(i, 0);
    }
    lca.setting();
    rep (i, 1, N + 1) used[i] = false;
    rep (i, 1, N + 1) {
        if (used[i]) continue;
        make_ans(i, 0);
    }

    cout << g << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3960kb

input:

4 4
1 2 1
2 3 1
3 4 1
4 1 1

output:

4

result:

ok answer is '4'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3852kb

input:

4 5
1 2 1
1 3 2
1 4 1
2 3 1
3 4 1

output:

4

result:

ok answer is '4'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3932kb

input:

20 50
1 2 8
1 3 1
3 4 5
3 5 9
3 6 5
6 7 6
7 8 8
2 9 2
8 10 3
8 11 7
8 12 5
3 13 4
7 14 3
6 15 7
9 16 6
8 17 7
16 18 9
16 19 3
18 20 10
11 3 2
17 1 1
16 2 2
15 1 1
10 3 2
9 1 2
19 2 1
6 1 2
7 3 1
17 3 2
15 3 2
8 6 2
5 1 2
8 1 2
12 1 1
12 7 1
4 1 2
18 2 1
11 7 1
14 1 1
18 1 1
18 9 1
10 6 1
14 3 2
20 2...

output:

2

result:

ok answer is '2'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3964kb

input:

20 50
1 2 18468
1 3 26501
3 4 15725
3 5 29359
3 6 24465
6 7 28146
7 8 16828
2 9 492
8 10 11943
8 11 5437
8 12 14605
3 13 154
7 14 12383
6 15 18717
9 16 19896
8 17 21727
16 18 11539
16 19 19913
18 20 26300
11 3 2
17 1 1
16 2 2
15 1 1
10 3 2
9 1 2
19 2 1
6 1 2
7 3 1
17 3 2
15 3 2
8 6 2
5 1 2
8 1 2
12 ...

output:

1

result:

ok answer is '1'

Test #5:

score: 0
Accepted
time: 1ms
memory: 4008kb

input:

100 150
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
11...

output:

3

result:

ok answer is '3'

Test #6:

score: 0
Accepted
time: 0ms
memory: 4152kb

input:

100 130
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
11...

output:

7

result:

ok answer is '7'

Test #7:

score: 0
Accepted
time: 1ms
memory: 4220kb

input:

100 200
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
11...

output:

4

result:

ok answer is '4'

Test #8:

score: 0
Accepted
time: 1ms
memory: 4176kb

input:

100 190
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
11...

output:

2

result:

ok answer is '2'

Test #9:

score: 0
Accepted
time: 2ms
memory: 4428kb

input:

1000 1500
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
...

output:

3

result:

ok answer is '3'

Test #10:

score: 0
Accepted
time: 2ms
memory: 4184kb

input:

1000 1500
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
...

output:

1

result:

ok answer is '1'

Test #11:

score: 0
Accepted
time: 3ms
memory: 4488kb

input:

1000 1600
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
...

output:

1

result:

ok answer is '1'

Test #12:

score: 0
Accepted
time: 1ms
memory: 4220kb

input:

100 190
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
11...

output:

4

result:

ok answer is '4'

Test #13:

score: 0
Accepted
time: 135ms
memory: 4668kb

input:

1000 3000
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
...

output:

2

result:

ok answer is '2'

Test #14:

score: 0
Accepted
time: 1ms
memory: 4248kb

input:

1000 1400
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
...

output:

1

result:

ok answer is '1'

Test #15:

score: 0
Accepted
time: 2ms
memory: 4276kb

input:

1000 1500
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
...

output:

2

result:

ok answer is '2'

Test #16:

score: 0
Accepted
time: 2ms
memory: 4276kb

input:

1000 1500
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
...

output:

8

result:

ok answer is '8'

Test #17:

score: 0
Accepted
time: 2ms
memory: 4360kb

input:

2000 2500
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

12

result:

ok answer is '12'

Test #18:

score: 0
Accepted
time: 2ms
memory: 4624kb

input:

2000 2500
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

2

result:

ok answer is '2'

Test #19:

score: 0
Accepted
time: 0ms
memory: 4424kb

input:

2000 2500
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

13

result:

ok answer is '13'

Test #20:

score: 0
Accepted
time: 2ms
memory: 4488kb

input:

2000 2500
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

1

result:

ok answer is '1'

Test #21:

score: 0
Accepted
time: 4ms
memory: 4480kb

input:

2000 3000
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

3

result:

ok answer is '3'

Test #22:

score: 0
Accepted
time: 4ms
memory: 4564kb

input:

2000 3000
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

1

result:

ok answer is '1'

Test #23:

score: 0
Accepted
time: 2ms
memory: 4408kb

input:

2000 2500
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

1

result:

ok answer is '1'

Test #24:

score: 0
Accepted
time: 20ms
memory: 4548kb

input:

2000 3500
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

2

result:

ok answer is '2'

Test #25:

score: 0
Accepted
time: 38ms
memory: 4864kb

input:

2000 4000
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

4

result:

ok answer is '4'

Test #26:

score: 0
Accepted
time: 2ms
memory: 4444kb

input:

2000 2300
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

1

result:

ok answer is '1'

Test #27:

score: 0
Accepted
time: 10ms
memory: 4912kb

input:

3000 5000
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

1

result:

ok answer is '1'

Test #28:

score: 0
Accepted
time: 0ms
memory: 4760kb

input:

3000 3700
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

13

result:

ok answer is '13'

Test #29:

score: 0
Accepted
time: 3ms
memory: 4760kb

input:

3000 3700
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

1

result:

ok answer is '1'

Test #30:

score: 0
Accepted
time: 11ms
memory: 5484kb

input:

5000 8000
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

3

result:

ok answer is '3'

Test #31:

score: 0
Accepted
time: 16ms
memory: 5516kb

input:

5000 8000
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

1

result:

ok answer is '1'

Test #32:

score: 0
Accepted
time: 8ms
memory: 5544kb

input:

5000 7200
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

5

result:

ok answer is '5'

Test #33:

score: 0
Accepted
time: 8ms
memory: 5620kb

input:

5000 7200
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

1

result:

ok answer is '1'

Test #34:

score: 0
Accepted
time: 15ms
memory: 5500kb

input:

5000 8000
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

6

result:

ok answer is '6'

Test #35:

score: 0
Accepted
time: 16ms
memory: 5396kb

input:

5000 8000
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

2

result:

ok answer is '2'

Test #36:

score: 0
Accepted
time: 135ms
memory: 5784kb

input:

5000 10000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 205804...

output:

4

result:

ok answer is '4'

Test #37:

score: 0
Accepted
time: 133ms
memory: 5792kb

input:

5000 10000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 205804...

output:

2

result:

ok answer is '2'

Test #38:

score: 0
Accepted
time: 4ms
memory: 5236kb

input:

5000 6000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

7

result:

ok answer is '7'

Test #39:

score: 0
Accepted
time: 4ms
memory: 5240kb

input:

5000 6000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

1

result:

ok answer is '1'

Test #40:

score: 0
Accepted
time: 4ms
memory: 5236kb

input:

5000 6000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

2

result:

ok answer is '2'

Test #41:

score: 0
Accepted
time: 4ms
memory: 5168kb

input:

5000 6000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

9

result:

ok answer is '9'

Test #42:

score: 0
Accepted
time: 5ms
memory: 5260kb

input:

5000 6666
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

9

result:

ok answer is '9'

Test #43:

score: 0
Accepted
time: 5ms
memory: 5316kb

input:

5000 6666
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

1

result:

ok answer is '1'

Test #44:

score: 0
Accepted
time: 3ms
memory: 5240kb

input:

5000 6000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

12345

result:

ok answer is '12345'

Test #45:

score: 0
Accepted
time: 3ms
memory: 5460kb

input:

5000 6000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

997

result:

ok answer is '997'

Test #46:

score: 0
Accepted
time: 3ms
memory: 5252kb

input:

5000 6000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

1

result:

ok answer is '1'

Test #47:

score: 0
Accepted
time: 2ms
memory: 5100kb

input:

5000 4999
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

0

result:

ok answer is '0'

Test #48:

score: 0
Accepted
time: 0ms
memory: 4180kb

input:

6 6
1 2 999999999
2 3 999999999
3 4 999999999
4 5 999999999
5 6 999999999
6 1 999999999

output:

5999999994

result:

ok answer is '5999999994'

Test #49:

score: 0
Accepted
time: 0ms
memory: 3960kb

input:

6 6
1 2 6
2 3 6
3 1 6
4 5 15
5 6 7
6 4 8

output:

6

result:

ok answer is '6'

Test #50:

score: 0
Accepted
time: 1ms
memory: 3912kb

input:

1 0

output:

0

result:

ok answer is '0'

Test #51:

score: 0
Accepted
time: 0ms
memory: 3960kb

input:

4 5
1 2 1
3 4 1
2 3 1
1 4 1
1 3 1

output:

1

result:

ok answer is '1'

Test #52:

score: 0
Accepted
time: 0ms
memory: 4112kb

input:

6 6
1 2 1
1 3 1
3 4 1
1 4 1
2 3 1
5 1 1

output:

1

result:

ok answer is '1'

Test #53:

score: 0
Accepted
time: 0ms
memory: 4112kb

input:

9 10
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
1 8 1
4 9 1
6 9 1

output:

4

result:

ok answer is '4'

Test #54:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

6 7
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
1 6 1
3 6 1

output:

2

result:

ok answer is '2'

Test #55:

score: 0
Accepted
time: 0ms
memory: 3976kb

input:

33 36
2 22 1
12 18 1
27 28 1
9 19 1
26 27 1
6 21 1
15 16 1
2 3 1
7 24 1
3 12 1
4 23 1
28 29 1
5 14 1
29 30 1
1 10 1
11 13 1
6 13 1
16 25 1
14 21 1
4 16 1
10 19 1
10 11 1
5 15 1
1 8 1
3 20 1
7 13 1
25 26 1
29 31 1
17 23 1
8 18 1
12 24 1
25 30 1
31 32 1
17 20 1
15 22 1
9 18 1

output:

3

result:

ok answer is '3'

Test #56:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

33 35
10 13 1
6 13 1
9 19 1
5 15 1
29 31 1
2 3 1
4 16 1
3 20 1
7 13 1
31 32 1
12 24 1
2 22 1
17 23 1
26 27 1
17 20 1
16 25 1
3 12 1
28 29 1
1 8 1
12 18 1
27 28 1
14 21 1
10 19 1
25 26 1
5 14 1
15 16 1
9 18 1
4 23 1
25 30 1
1 10 1
8 18 1
7 24 1
29 30 1
6 21 1
15 22 1

output:

1

result:

ok answer is '1'

Test #57:

score: 0
Accepted
time: 1ms
memory: 4648kb

input:

2000 2000
1036 1254 1
1453 1496 1
342 1815 1
186 346 1
840 1555 1
138 1503 1
416 1376 1
660 1253 1
1279 1799 1
209 1554 1
624 1278 1
792 884 1
333 1703 1
393 894 1
551 1192 1
1705 1805 1
302 930 1
115 1384 1
151 1156 1
71 209 1
82 1637 1
858 1854 1
19 1798 1
348 703 1
1692 1744 1
261 1029 1
143 1631...

output:

2000

result:

ok answer is '2000'

Test #58:

score: 0
Accepted
time: 1ms
memory: 4384kb

input:

1820 1872
677 1254 1
114 163 1
1751 1815 1
532 1640 1
290 380 1
253 1429 1
174 1163 1
1005 1431 1
521 1324 1
37 1553 1
369 1764 1
658 1170 1
1456 1574 1
224 663 1
752 1460 1
128 441 1
831 1013 1
730 1583 1
500 983 1
374 1274 1
1394 1478 1
422 1223 1
1310 1632 1
1133 1508 1
914 1258 1
151 907 1
221 2...

output:

18

result:

ok answer is '18'

Test #59:

score: 0
Accepted
time: 0ms
memory: 4404kb

input:

1521 1584
1138 1283 1
95 542 1
137 1042 1
1043 1390 1
147 1396 1
382 709 1
651 828 1
909 1124 1
286 1485 1
31 171 1
925 1254 1
360 501 1
900 1229 1
69 1358 1
166 199 1
633 1178 1
310 1390 1
679 1482 1
844 1333 1
761 1208 1
38 1512 1
449 875 1
13 1467 1
77 217 1
622 736 1
45 1163 1
365 1346 1
106 108...

output:

12

result:

ok answer is '12'

Test #60:

score: 0
Accepted
time: 2ms
memory: 4576kb

input:

1433 1467
43 1268 1
90 1143 1
237 271 1
444 1375 1
232 1407 1
1026 1139 1
861 943 1
981 1003 1
77 1229 1
416 966 1
606 1370 1
351 438 1
687 1379 1
1030 1186 1
1373 1428 1
715 762 1
553 1426 1
238 1012 1
120 618 1
345 857 1
827 1118 1
548 1085 1
245 333 1
82 910 1
202 570 1
80 781 1
666 797 1
122 102...

output:

9

result:

ok answer is '9'

Test #61:

score: 0
Accepted
time: 0ms
memory: 4384kb

input:

1569 1625
1043 1553 1
57 369 1
481 1231 1
99 227 1
113 262 1
239 354 1
175 887 1
819 1230 1
27 115 1
76 820 1
1086 1498 1
482 1193 1
1299 1447 1
570 604 1
121 508 1
100 208 1
77 572 1
52 1296 1
198 639 1
103 945 1
256 381 1
745 1173 1
1033 1350 1
13 1414 1
233 1399 1
402 1417 1
1394 1441 1
206 623 1...

output:

5

result:

ok answer is '5'

Test #62:

score: 0
Accepted
time: 0ms
memory: 4192kb

input:

1035 1072
448 654 1
201 211 1
139 650 1
224 255 1
430 883 1
494 517 1
199 999 1
717 763 1
661 813 1
145 574 1
68 908 1
626 990 1
7 805 1
54 875 1
600 968 1
279 462 1
335 543 1
266 665 1
598 676 1
177 447 1
790 1034 1
273 909 1
475 814 1
464 973 1
210 560 1
290 905 1
650 708 1
288 994 1
10 183 1
261 ...

output:

8

result:

ok answer is '8'

Test #63:

score: 0
Accepted
time: 1ms
memory: 3964kb

input:

162 198
41 83 1
15 121 1
29 76 1
62 75 1
78 114 1
58 80 1
5 75 1
85 119 1
45 137 1
3 56 1
149 156 1
46 63 1
79 107 1
125 150 1
33 78 1
43 149 1
27 87 1
20 33 1
13 136 1
60 90 1
60 110 1
30 97 1
102 152 1
25 31 1
6 79 1
24 67 1
16 78 1
68 115 1
77 78 1
103 124 1
117 161 1
117 139 1
55 67 1
19 146 1
4...

output:

3

result:

ok answer is '3'

Test #64:

score: 0
Accepted
time: 1ms
memory: 4500kb

input:

1894 1932
384 1664 1
1204 1508 1
733 1583 1
818 1515 1
879 1799 1
197 1165 1
657 919 1
559 1893 1
241 1104 1
347 1283 1
516 916 1
179 1041 1
305 477 1
1116 1135 1
1254 1561 1
280 742 1
269 975 1
34 862 1
1033 1659 1
74 382 1
307 1600 1
99 1553 1
1298 1565 1
955 1579 1
308 478 1
947 1595 1
1686 1793 ...

output:

7

result:

ok answer is '7'

Test #65:

score: 0
Accepted
time: 151ms
memory: 4240kb

input:

63 1953
24 25 1
30 53 1
16 28 1
20 36 1
34 51 1
33 52 1
3 11 1
9 35 1
28 52 1
52 54 1
22 51 1
33 46 1
2 45 1
35 43 1
4 48 1
4 35 1
2 7 1
26 59 1
21 35 1
21 43 1
9 58 1
37 63 1
7 26 1
17 32 1
7 11 1
34 56 1
6 54 1
18 62 1
33 44 1
15 52 1
50 53 1
17 46 1
12 42 1
9 31 1
9 11 1
35 47 1
1 13 1
21 42 1
26...

output:

1

result:

ok answer is '1'

Test #66:

score: 0
Accepted
time: 186ms
memory: 4184kb

input:

89 1939
29 62 1
14 25 1
5 60 1
24 26 1
1 8 1
3 68 1
47 85 1
41 81 1
47 55 1
22 75 1
20 37 1
42 87 1
46 53 1
48 55 1
54 72 1
61 66 1
7 43 1
70 74 1
63 89 1
29 51 1
21 56 1
18 49 1
20 31 1
14 34 1
22 85 1
75 86 1
52 68 1
12 32 1
44 55 1
41 42 1
37 82 1
36 82 1
5 67 1
52 74 1
5 18 1
35 40 1
14 60 1
11 ...

output:

1

result:

ok answer is '1'

Test #67:

score: 0
Accepted
time: 157ms
memory: 4360kb

input:

409 1944
69 134 1
162 172 1
50 327 1
3 17 1
152 256 1
19 302 1
246 371 1
289 394 1
228 376 1
210 270 1
318 336 1
352 405 1
171 324 1
21 398 1
70 236 1
68 349 1
316 344 1
84 386 1
223 344 1
125 223 1
293 327 1
88 253 1
39 165 1
151 395 1
201 322 1
68 403 1
336 383 1
215 256 1
73 138 1
5 399 1
260 268...

output:

1

result:

ok answer is '1'

Test #68:

score: 0
Accepted
time: 116ms
memory: 4276kb

input:

509 1828
245 248 1
384 386 1
127 261 1
260 480 1
437 466 1
127 382 1
158 476 1
482 498 1
241 375 1
159 216 1
232 408 1
74 270 1
32 293 1
126 249 1
59 445 1
146 291 1
129 234 1
81 164 1
243 437 1
258 262 1
229 320 1
126 185 1
118 423 1
221 488 1
185 204 1
220 227 1
96 472 1
112 149 1
106 432 1
46 100...

output:

2

result:

ok answer is '2'

Test #69:

score: 0
Accepted
time: 0ms
memory: 4664kb

input:

2000 1999
1552 1932 1
553 1152 1
1006 1967 1
606 1381 1
1549 1775 1
1283 1992 1
994 1000 1
367 1864 1
1047 1989 1
475 1284 1
1033 1688 1
827 1786 1
746 1018 1
651 756 1
73 1178 1
307 539 1
114 1924 1
653 667 1
693 1087 1
222 1656 1
241 1841 1
165 1725 1
433 476 1
66 1099 1
169 1490 1
609 1257 1
506 ...

output:

1440

result:

ok answer is '1440'

Test #70:

score: 0
Accepted
time: 1ms
memory: 4376kb

input:

1302 1302
893 1045 1
149 798 1
202 1034 1
252 789 1
269 920 1
915 989 1
96 496 1
1142 1302 1
647 868 1
54 1127 1
161 704 1
128 1294 1
51 718 1
325 825 1
423 798 1
344 809 1
504 1070 1
548 756 1
276 1116 1
8 41 1
782 1294 1
602 685 1
137 976 1
315 1028 1
75 562 1
36 1208 1
20 302 1
383 1080 1
62 392 ...

output:

42

result:

ok answer is '42'

Test #71:

score: 0
Accepted
time: 1ms
memory: 4512kb

input:

1932 1989
390 911 1
1384 1761 1
679 791 1
931 1855 1
315 1346 1
201 331 1
167 1560 1
72 1206 1
255 1838 1
1777 1854 1
693 1869 1
1225 1343 1
588 825 1
904 1120 1
413 773 1
853 1521 1
884 924 1
628 638 1
370 1080 1
1004 1821 1
342 817 1
1315 1448 1
289 352 1
1389 1730 1
921 1602 1
880 1307 1
164 263 ...

output:

17

result:

ok answer is '17'

Test #72:

score: 0
Accepted
time: 1ms
memory: 4132kb

input:

561 572
290 330 1
81 158 1
158 166 1
501 548 1
387 482 1
54 121 1
521 535 1
106 397 1
263 466 1
230 520 1
332 400 1
55 374 1
182 209 1
138 219 1
154 506 1
494 510 1
45 346 1
190 421 1
290 383 1
56 361 1
123 157 1
380 538 1
345 525 1
225 318 1
82 356 1
40 340 1
245 451 1
420 520 1
470 556 1
279 347 1...

output:

13

result:

ok answer is '13'

Test #73:

score: 0
Accepted
time: 1ms
memory: 4328kb

input:

573 585
96 357 1
358 495 1
136 375 1
200 538 1
1 112 1
170 524 1
125 273 1
189 572 1
525 562 1
24 443 1
152 173 1
224 250 1
470 572 1
76 299 1
289 371 1
161 561 1
269 435 1
114 122 1
225 442 1
65 175 1
207 319 1
73 469 1
6 327 1
144 357 1
389 557 1
256 534 1
398 413 1
87 413 1
519 567 1
312 353 1
40...

output:

1

result:

ok answer is '1'

Test #74:

score: 0
Accepted
time: 1ms
memory: 3956kb

input:

230 246
13 198 1
31 100 1
54 181 1
10 211 1
210 218 1
151 178 1
175 228 1
66 164 1
15 81 1
156 214 1
36 200 1
154 228 1
73 84 1
57 210 1
127 144 1
81 167 1
131 154 1
40 143 1
86 157 1
48 58 1
208 230 1
164 230 1
4 132 1
22 159 1
67 138 1
63 78 1
171 184 1
69 121 1
51 209 1
9 38 1
111 167 1
65 75 1
1...

output:

6

result:

ok answer is '6'

Test #75:

score: 0
Accepted
time: 1ms
memory: 4008kb

input:

436 468
328 330 1
46 78 1
219 400 1
165 329 1
278 391 1
45 387 1
166 402 1
66 213 1
102 358 1
185 368 1
91 136 1
33 378 1
73 102 1
111 150 1
95 405 1
150 402 1
6 223 1
119 351 1
110 381 1
178 407 1
175 212 1
379 416 1
153 310 1
198 241 1
259 319 1
114 177 1
66 341 1
26 354 1
302 364 1
232 385 1
175 ...

output:

9

result:

ok answer is '9'

Test #76:

score: 0
Accepted
time: 1ms
memory: 4252kb

input:

2000 714
13 198 1
31 100 1
54 181 1
10 211 1
210 218 1
151 178 1
175 228 1
66 164 1
15 81 1
156 214 1
36 200 1
154 228 1
73 84 1
57 210 1
127 144 1
81 167 1
131 154 1
40 143 1
86 157 1
48 58 1
208 230 1
164 230 1
4 132 1
22 159 1
67 138 1
63 78 1
171 184 1
69 121 1
51 209 1
9 38 1
111 167 1
65 75 1
...

output:

3

result:

ok answer is '3'

Test #77:

score: 0
Accepted
time: 1ms
memory: 4284kb

input:

2000 715
13 198 1
31 100 1
54 181 1
10 211 1
210 218 1
151 178 1
175 228 1
66 164 1
15 81 1
156 214 1
36 200 1
154 228 1
73 84 1
57 210 1
127 144 1
81 167 1
131 154 1
40 143 1
86 157 1
48 58 1
208 230 1
164 230 1
4 132 1
22 159 1
67 138 1
63 78 1
171 184 1
69 121 1
51 209 1
9 38 1
111 167 1
65 75 1
...

output:

3

result:

ok answer is '3'

Test #78:

score: 0
Accepted
time: 1ms
memory: 4424kb

input:

1725 1990
597 1010 1
914 1360 1
1005 1490 1
854 944 1
292 383 1
230 745 1
259 1658 1
944 1281 1
485 586 1
193 1268 1
1231 1375 1
1409 1472 1
1069 1451 1
1409 1630 1
252 1304 1
766 988 1
1122 1458 1
265 1682 1
510 1078 1
775 845 1
138 1030 1
435 743 1
1040 1357 1
278 986 1
754 872 1
493 1645 1
1144 1...

output:

5

result:

ok answer is '5'

Test #79:

score: 0
Accepted
time: 1ms
memory: 4440kb

input:

1827 1992
620 1798 1
467 1613 1
264 1212 1
200 258 1
1660 1729 1
74 1326 1
327 1069 1
1051 1363 1
428 501 1
78 1439 1
513 1393 1
343 855 1
705 1396 1
370 897 1
553 1323 1
190 1776 1
1137 1192 1
194 1767 1
841 1068 1
99 1216 1
1378 1439 1
332 1012 1
132 443 1
243 914 1
944 1419 1
1177 1523 1
87 1818 ...

output:

4

result:

ok answer is '4'

Test #80:

score: 0
Accepted
time: 1ms
memory: 4416kb

input:

1760 1980
536 1508 1
254 1599 1
1064 1521 1
319 1216 1
866 1361 1
279 647 1
39 227 1
1530 1537 1
568 1676 1
1156 1242 1
916 1597 1
409 927 1
91 909 1
815 1001 1
160 1278 1
195 1007 1
39 848 1
493 1386 1
55 1288 1
476 1624 1
1304 1745 1
43 1521 1
217 602 1
661 1499 1
13 1695 1
1184 1428 1
144 335 1
8...

output:

3

result:

ok answer is '3'

Test #81:

score: 0
Accepted
time: 1ms
memory: 4372kb

input:

1856 1990
799 1430 1
856 1191 1
151 1851 1
793 1353 1
117 1144 1
858 936 1
890 1110 1
714 740 1
1158 1754 1
1394 1849 1
555 1652 1
416 1077 1
1706 1751 1
267 1394 1
64 714 1
88 1334 1
903 1087 1
204 290 1
622 1772 1
520 725 1
381 798 1
506 1794 1
305 1660 1
37 66 1
10 619 1
1270 1692 1
264 634 1
598...

output:

5

result:

ok answer is '5'

Test #82:

score: 0
Accepted
time: 1ms
memory: 4968kb

input:

1997 1998
994 1781 1
670 1387 1
843 1075 1
1277 1770 1
784 1533 1
675 1192 1
1047 1323 1
267 1405 1
561 565 1
681 1749 1
243 421 1
31 1798 1
537 1856 1
1757 1878 1
1941 1986 1
25 1465 1
759 1587 1
6 1133 1
549 1044 1
1429 1819 1
557 1346 1
363 1761 1
936 1147 1
487 855 1
1931 1978 1
1339 1484 1
220 ...

output:

1332

result:

ok answer is '1332'

Test #83:

score: 0
Accepted
time: 1ms
memory: 4388kb

input:

1652 1988
1297 1437 1
315 389 1
138 1096 1
1317 1474 1
1310 1315 1
194 601 1
939 977 1
332 1295 1
275 1502 1
1039 1326 1
878 1248 1
1034 1293 1
283 454 1
1372 1452 1
942 996 1
1133 1226 1
285 1111 1
537 1291 1
459 1200 1
799 1074 1
811 1620 1
582 1190 1
714 1376 1
695 1117 1
1198 1305 1
778 869 1
19...

output:

2

result:

ok answer is '2'

Test #84:

score: 0
Accepted
time: 1ms
memory: 4440kb

input:

1772 1986
777 1502 1
1511 1719 1
1324 1385 1
1412 1491 1
302 1246 1
451 1258 1
1201 1407 1
850 872 1
1002 1292 1
866 1150 1
572 1748 1
1084 1210 1
234 1105 1
736 854 1
1015 1068 1
599 637 1
1172 1549 1
1545 1623 1
222 694 1
512 1268 1
424 592 1
877 1315 1
3 237 1
466 1366 1
1060 1692 1
437 1101 1
12...

output:

3

result:

ok answer is '3'

Test #85:

score: 0
Accepted
time: 1ms
memory: 4432kb

input:

1817 1984
387 625 1
1077 1128 1
1222 1780 1
2 739 1
1184 1626 1
1 681 1
1269 1360 1
244 1129 1
602 1304 1
703 1244 1
1631 1697 1
404 1769 1
110 1618 1
890 1140 1
1239 1787 1
12 360 1
209 681 1
345 1451 1
923 1322 1
128 1795 1
263 979 1
315 1393 1
689 1073 1
20 1340 1
10 34 1
961 1669 1
471 1739 1
12...

output:

4

result:

ok answer is '4'

Test #86:

score: 0
Accepted
time: 0ms
memory: 4328kb

input:

1834 1970
510 1085 1
329 1732 1
348 535 1
417 1573 1
936 1111 1
668 1591 1
235 1702 1
60 1179 1
1334 1354 1
167 1122 1
128 1518 1
349 958 1
390 807 1
473 1370 1
461 1131 1
75 380 1
922 1433 1
288 419 1
265 847 1
358 803 1
319 412 1
1439 1527 1
348 458 1
1015 1539 1
1553 1799 1
256 1055 1
269 1304 1
...

output:

10

result:

ok answer is '10'

Test #87:

score: 0
Accepted
time: 1ms
memory: 4376kb

input:

1849 1956
1513 1642 1
503 1259 1
962 1582 1
1164 1313 1
753 1103 1
80 890 1
135 1241 1
1177 1483 1
923 1479 1
745 1548 1
448 1119 1
228 1354 1
1206 1388 1
840 1479 1
1686 1807 1
1360 1427 1
161 1456 1
772 1424 1
929 1066 1
401 877 1
230 1753 1
1676 1820 1
500 1292 1
478 759 1
455 1559 1
918 1135 1
2...

output:

6

result:

ok answer is '6'

Test #88:

score: 0
Accepted
time: 0ms
memory: 4452kb

input:

1891 1988
679 1696 1
208 1175 1
202 1118 1
354 1713 1
137 1183 1
152 1634 1
829 1129 1
558 712 1
758 1322 1
1050 1789 1
446 952 1
468 904 1
259 1705 1
560 652 1
589 1308 1
1163 1713 1
988 1150 1
697 1534 1
128 324 1
7 895 1
1023 1515 1
1710 1876 1
1486 1571 1
160 743 1
249 1884 1
14 1000 1
651 1154 ...

output:

7

result:

ok answer is '7'

Test #89:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

6 7
1 2 1
2 3 1
1 4 1
2 5 1
3 6 1
4 5 1
5 6 1

output:

2

result:

ok answer is '2'

Test #90:

score: 0
Accepted
time: 0ms
memory: 3972kb

input:

8 10
1 2 1
1 3 1
2 4 1
3 4 1
1 5 1
4 8 1
5 6 1
5 7 1
6 8 1
7 8 1

output:

2

result:

ok answer is '2'

Test #91:

score: 0
Accepted
time: 0ms
memory: 3892kb

input:

5 10
2 5 1
1 4 1
2 4 1
4 5 1
1 2 1
1 3 1
2 3 1
1 5 1
3 4 1
3 5 1

output:

1

result:

ok answer is '1'

Test #92:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

7 18
5 7 1
2 3 1
3 4 1
4 6 1
4 7 1
3 5 1
1 2 1
1 6 1
4 5 1
3 7 1
5 6 1
2 4 1
2 7 1
1 7 1
1 4 1
3 6 1
1 3 1
2 5 1

output:

1

result:

ok answer is '1'

Test #93:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

7 7
1 7 1
2 4 1
4 5 1
3 6 1
1 2 1
3 7 1
5 6 1

output:

7

result:

ok answer is '7'

Test #94:

score: 0
Accepted
time: 0ms
memory: 3976kb

input:

7 7
6 7 1
3 6 1
2 5 1
1 4 1
1 2 1
3 4 1
5 7 1

output:

7

result:

ok answer is '7'

Test #95:

score: 0
Accepted
time: 0ms
memory: 3988kb

input:

26 28
7 12 1
2 6 1
4 23 1
4 26 1
11 19 1
6 13 1
1 3 1
18 23 1
15 17 1
14 21 1
10 11 1
9 22 1
16 20 1
11 22 1
8 14 1
8 24 1
12 21 1
15 20 1
1 14 1
10 13 1
5 19 1
5 25 1
9 18 1
7 25 1
2 24 1
11 16 1
14 26 1
3 17 1

output:

14

result:

ok answer is '14'

Test #96:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

34 36
25 31 1
27 28 1
4 16 1
21 30 1
12 32 1
1 21 1
14 17 1
11 18 1
10 22 1
5 7 1
19 33 1
2 9 1
31 33 1
14 24 1
7 22 1
4 24 1
13 26 1
12 23 1
8 32 1
21 34 1
15 23 1
6 20 1
21 28 1
2 17 1
15 18 1
5 34 1
25 29 1
3 27 1
4 13 1
16 20 1
4 11 1
8 30 1
6 10 1
3 9 1
1 29 1
19 26 1

output:

18

result:

ok answer is '18'

Test #97:

score: 0
Accepted
time: 0ms
memory: 3964kb

input:

38 39
15 33 1
1 18 1
10 14 1
23 34 1
24 30 1
16 28 1
17 34 1
2 21 1
4 20 1
13 32 1
9 37 1
3 13 1
12 16 1
2 27 1
23 30 1
8 35 1
18 33 1
6 31 1
29 35 1
5 38 1
6 20 1
11 22 1
21 25 1
31 36 1
1 4 1
28 37 1
11 14 1
5 19 1
20 26 1
8 38 1
15 22 1
24 25 1
9 27 1
30 32 1
7 12 1
19 36 1
17 29 1
3 10 1
7 26 1

output:

26

result:

ok answer is '26'

Test #98:

score: 0
Accepted
time: 1ms
memory: 3864kb

input:

67 70
22 48 1
56 60 1
38 51 1
41 50 1
3 52 1
30 64 1
31 40 1
2 59 1
11 53 1
60 63 1
9 24 1
3 43 1
41 47 1
7 58 1
19 42 1
18 63 1
27 40 1
12 25 1
15 26 1
38 56 1
8 51 1
1 16 1
6 7 1
17 46 1
10 26 1
11 29 1
2 37 1
57 58 1
9 36 1
45 65 1
49 66 1
35 46 1
4 62 1
4 19 1
25 47 1
14 24 1
1 43 1
2 44 1
3 13 ...

output:

10

result:

ok answer is '10'

Test #99:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

22 27
8 18 1
6 7 1
18 20 1
1 11 1
5 11 1
5 7 1
17 19 1
9 13 1
1 13 1
3 8 1
4 10 1
16 19 1
5 21 1
14 22 1
14 15 1
2 17 1
15 20 1
17 18 1
3 14 1
12 18 1
4 13 1
5 10 1
5 16 1
9 14 1
2 21 1
12 22 1
6 13 1

output:

6

result:

ok answer is '6'

Test #100:

score: 0
Accepted
time: 1ms
memory: 3920kb

input:

11 12
1 8 1
2 5 1
1 10 1
7 11 1
2 8 1
3 5 1
10 11 1
4 6 1
2 4 1
9 11 1
3 9 1
6 7 1

output:

8

result:

ok answer is '8'

Test #101:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

15 15
1 4 1
6 14 1
9 14 1
11 13 1
3 13 1
1 15 1
10 12 1
3 11 1
7 10 1
2 8 1
7 12 1
5 8 1
2 5 1
4 15 1
6 9 1

output:

3

result:

ok answer is '3'

Test #102:

score: 0
Accepted
time: 86ms
memory: 4360kb

input:

743 1798
235 488 1
105 586 1
91 424 1
100 313 1
270 447 1
15 683 1
21 552 1
65 634 1
296 561 1
642 722 1
49 140 1
125 380 1
125 433 1
410 545 1
469 521 1
151 264 1
49 672 1
301 393 1
12 118 1
253 446 1
468 603 1
86 296 1
322 568 1
115 589 1
420 540 1
379 426 1
516 700 1
96 332 1
86 334 1
440 597 1
4...

output:

1

result:

ok answer is '1'

Test #103:

score: 0
Accepted
time: 14ms
memory: 4420kb

input:

1394 1624
112 956 1
548 702 1
390 996 1
16 1108 1
532 792 1
600 966 1
542 947 1
708 909 1
15 1186 1
1208 1266 1
517 1262 1
242 290 1
1020 1343 1
787 1124 1
331 373 1
1157 1362 1
44 313 1
475 1354 1
72 1073 1
228 831 1
281 1063 1
990 1014 1
67 1073 1
405 741 1
181 946 1
278 463 1
1006 1389 1
117 1130...

output:

1

result:

ok answer is '1'

Test #104:

score: 0
Accepted
time: 1ms
memory: 4592kb

input:

1517 1517
261 1340 1
451 838 1
933 1413 1
645 1207 1
872 1304 1
163 396 1
663 890 1
1128 1338 1
65 668 1
479 1187 1
212 720 1
41 1160 1
114 658 1
243 705 1
139 891 1
188 259 1
434 1134 1
88 1048 1
427 1220 1
663 929 1
643 1436 1
214 377 1
170 1255 1
130 875 1
161 243 1
821 1021 1
572 1501 1
589 867 ...

output:

1517

result:

ok answer is '1517'

Test #105:

score: 0
Accepted
time: 1ms
memory: 4368kb

input:

1199 1199
209 551 1
50 248 1
221 921 1
781 1197 1
933 1173 1
191 512 1
56 470 1
100 163 1
150 1130 1
335 336 1
675 760 1
187 797 1
82 158 1
595 690 1
382 920 1
311 617 1
374 1064 1
409 1016 1
436 835 1
4 702 1
526 1022 1
258 890 1
108 305 1
430 770 1
35 164 1
679 755 1
861 1024 1
648 716 1
28 318 1
...

output:

1199

result:

ok answer is '1199'

Test #106:

score: 0
Accepted
time: 1ms
memory: 4464kb

input:

1906 1918
83 1481 1
34 1495 1
1339 1894 1
64 1634 1
706 1438 1
1000 1350 1
456 1174 1
199 783 1
450 662 1
579 1884 1
980 1373 1
773 1042 1
167 680 1
344 1813 1
1252 1810 1
459 604 1
1338 1816 1
776 961 1
659 825 1
675 685 1
1160 1872 1
1147 1383 1
184 1047 1
674 1592 1
262 1687 1
284 774 1
611 982 1...

output:

274

result:

ok answer is '274'

Test #107:

score: 0
Accepted
time: 1ms
memory: 4416kb

input:

1892 1911
869 1615 1
130 1349 1
19 1685 1
498 727 1
53 1693 1
936 1797 1
74 1442 1
640 1235 1
87 1751 1
1010 1579 1
1047 1282 1
1547 1659 1
253 993 1
200 376 1
267 1411 1
237 1465 1
268 845 1
289 1381 1
350 1566 1
1192 1646 1
981 1199 1
550 861 1
820 1197 1
456 1005 1
299 1488 1
331 388 1
1054 1323 ...

output:

182

result:

ok answer is '182'

Test #108:

score: 0
Accepted
time: 0ms
memory: 4388kb

input:

1280 1292
204 586 1
641 1207 1
157 820 1
301 448 1
120 952 1
39 290 1
98 986 1
945 1100 1
331 1191 1
1078 1230 1
542 1143 1
193 800 1
352 928 1
22 75 1
462 601 1
373 514 1
138 449 1
630 1238 1
873 879 1
115 377 1
85 821 1
485 712 1
865 930 1
222 666 1
991 1034 1
760 978 1
181 287 1
605 1173 1
528 11...

output:

38

result:

ok answer is '38'

Test #109:

score: 0
Accepted
time: 1ms
memory: 4544kb

input:

1696 1712
406 413 1
472 712 1
380 971 1
1559 1647 1
42 1687 1
673 1416 1
583 1061 1
1169 1369 1
1232 1570 1
1069 1649 1
947 1138 1
1163 1301 1
71 74 1
923 1195 1
699 1276 1
1183 1519 1
268 663 1
779 1210 1
232 581 1
240 636 1
703 997 1
599 1139 1
275 399 1
834 1094 1
365 434 1
57 803 1
539 1431 1
50...

output:

32

result:

ok answer is '32'

Test #110:

score: 0
Accepted
time: 1ms
memory: 4576kb

input:

1743 1808
823 1061 1
830 1678 1
159 782 1
167 856 1
135 320 1
76 1643 1
1011 1220 1
275 1305 1
30 239 1
235 681 1
195 597 1
190 904 1
535 1153 1
851 1226 1
27 1568 1
620 1243 1
743 1657 1
387 1477 1
107 1639 1
562 1580 1
38 678 1
820 1145 1
663 1193 1
230 527 1
519 890 1
587 953 1
900 1572 1
683 105...

output:

16

result:

ok answer is '16'

Test #111:

score: 0
Accepted
time: 1ms
memory: 4500kb

input:

1392 1464
695 833 1
909 992 1
597 1351 1
153 543 1
225 579 1
346 612 1
491 805 1
773 1018 1
526 664 1
836 842 1
822 1074 1
408 702 1
1068 1266 1
880 1041 1
469 1371 1
1191 1334 1
10 575 1
285 1313 1
1317 1365 1
399 424 1
630 848 1
289 1259 1
97 796 1
681 1208 1
1044 1322 1
472 843 1
1151 1348 1
1227...

output:

12

result:

ok answer is '12'

Test #112:

score: 0
Accepted
time: 1ms
memory: 4440kb

input:

1998 1998
484 1576 1
894 1330 1
953 1124 1
1101 1534 1
24 1170 1
1029 1459 1
502 1817 1
729 1462 1
840 1714 1
81 1635 1
1247 1583 1
774 779 1
23 784 1
287 1001 1
1468 1549 1
355 538 1
739 1353 1
102 984 1
385 910 1
679 1287 1
836 1610 1
905 1539 1
387 655 1
276 1469 1
551 1841 1
49 1700 1
914 1241 1...

output:

3

result:

ok answer is '3'

Test #113:

score: 0
Accepted
time: 0ms
memory: 4112kb

input:

5 7
1 3 3
2 5 4
2 3 7
2 4 2
3 5 10
1 4 3
3 4 6

output:

1

result:

ok answer is '1'

Test #114:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

5 8
3 4 5
2 4 7
2 5 5
1 2 7
3 5 6
1 5 8
4 5 1
1 4 6

output:

1

result:

ok answer is '1'

Test #115:

score: 0
Accepted
time: 0ms
memory: 3980kb

input:

7 10
5 6 3
4 5 10
3 4 6
3 7 1
1 3 3
3 5 10
2 4 3
4 7 3
4 6 6
6 7 8

output:

1

result:

ok answer is '1'

Test #116:

score: 0
Accepted
time: 0ms
memory: 4108kb

input:

7 11
1 6 3
3 7 7
5 7 9
2 7 4
1 4 9
2 3 5
1 5 9
6 7 6
5 6 9
4 7 3
4 5 4

output:

1

result:

ok answer is '1'

Test #117:

score: 0
Accepted
time: 0ms
memory: 3992kb

input:

10 20
4 9 1
1 9 8
2 6 9
6 10 9
6 8 4
1 3 2
1 6 5
3 7 7
2 4 6
8 10 10
5 8 10
3 8 7
1 8 4
1 5 7
5 9 4
4 5 6
7 8 8
6 7 2
2 10 8
1 7 7

output:

1

result:

ok answer is '1'

Test #118:

score: 0
Accepted
time: 0ms
memory: 3984kb

input:

10 14
1 9 5
3 8 9
8 9 4
2 9 5
2 3 7
5 6 10
1 4 9
3 7 4
1 3 5
3 6 1
7 9 6
4 8 7
1 2 2
6 8 8

output:

1

result:

ok answer is '1'

Test #119:

score: 0
Accepted
time: 0ms
memory: 4148kb

input:

12 17
11 12 6
1 10 5
3 10 7
3 8 6
7 8 8
4 6 7
2 9 1
3 9 9
3 5 3
4 8 2
2 8 2
5 10 10
3 6 5
4 11 6
1 11 1
2 12 8
7 11 4

output:

1

result:

ok answer is '1'

Test #120:

score: 0
Accepted
time: 0ms
memory: 3996kb

input:

12 16
11 12 6
1 10 5
3 10 7
3 8 6
7 8 8
4 6 7
2 9 1
3 9 9
3 5 3
4 8 2
2 8 2
5 10 10
3 6 5
4 11 6
1 11 1
2 12 8

output:

1

result:

ok answer is '1'

Test #121:

score: -100
Time Limit Exceeded

input:

500 10000
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 13 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 22 1
22 23 1
23 24 1
24 25 1
25 26 1
26 27 1
27 28 1
28 29 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 1
37 38 1
38 39 1
39 ...

output:


result: