QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#217601#7177. Many Many CyclesLainTL 1981ms102400kbC++202.6kb2023-10-17 02:15:512023-10-17 02:15:52

Judging History

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

  • [2023-10-17 02:15:52]
  • 评测
  • 测评结果:TL
  • 用时:1981ms
  • 内存:102400kb
  • [2023-10-17 02:15:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;


int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

  struct edge {
    int u, v, w, is_span;
    int to(int x) {
      return u^v^x;
    }
  };

  int n, m;
  cin >> n >> m;
  vector<edge> edges;
  edges.reserve(m);
  vector<vi> g(n);
  rep(i, 0, m) {
    int u, v, w;
    cin >> u >> v >> w;
    u--,v--;
    g[u].push_back(sz(edges));
    g[v].push_back(sz(edges));
    edges.push_back({u,v,w,0});
  }


  const int B = 14;
  vector<vi> up(n, vi(B));
  int comp_num = 0;
  vi vis(n), comp(n), dep(n);
  vector<ll> dist(n);
  auto dfs = [&](auto& self, int s, int p)->void {
    up[s][0] = p;
    rep(j, 1, B) up[s][j] = up[up[s][j-1]][j-1];
    vis[s] = 1;
    comp[s] = comp_num;
    for (auto& e : g[s]) {
      int u = edges[e].to(s);
      if (vis[u]) continue;
      edges[e].is_span = 1;
      dist[u] = dist[s] + edges[e].w;
      dep[u] = dep[s]+1;
      self(self, u, s);
    }
  };
  rep(i, 0, n)  {
    if (!vis[i]) {
      dfs(dfs, i, i);
      comp_num++;
    }
  }

  vector<vi> memo(n, vi(n, -1));
  auto lca = [&](int x, int y)->int {
    if (memo[x][y] != -1) return memo[x][y];
    if (dep[x] > dep[y]) swap(x, y);
    if (x == y) return x;
    int diff = dep[y] - dep[x];
    rep(j, 0, B) {
      if (diff>>j&1) y = up[y][j];
    }
    if (x == y) return memo[x][y] = memo[y][x] = x;
    for (int j = B-1; j >= 0; j--) {
      if (up[x][j] != up[y][j]) {
        x = up[x][j], y = up[y][j];
      }
    }
    return memo[x][y] = memo[y][x] = up[x][0];
  };

  ll ans = 0;
  rep(i, 0, m) {
    auto [u,v, w, is_span] = edges[i];
    if (is_span) continue;

    if (dep[u] > dep[v]) swap(u, v); // u above v
    
    // Simple cycle
    ans = __gcd(ans, dist[v] - dist[u] + w);

    // xored
    rep(j, i+1, m) {
      if (edges[j].is_span) continue;
      auto [a, b, w1, _] = edges[j];
      if (comp[a] != comp[u]) continue; // not in the same component, ignore
      if (dep[a] > dep[b]) swap(a, b); // a above b
      if (dep[b] <= dep[u]) continue; // no intersection, b above u
      int upper = dep[a] < dep[u] ? a : u;
      int lower = dep[a] > dep[u] ? a : u;
      if (lca(upper, lower) != upper) continue; // no shared edges
      int l = lca(v, b);
      if (dep[l] <= dep[lower]) continue;
      ans = __gcd(ans, 2*(dist[l] - dist[lower]));
    }
  }
  cout << ans << '\n';
}


详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3792kb

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: 0ms
memory: 3816kb

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: 0ms
memory: 3636kb

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: 0ms
memory: 3568kb

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: 0ms
memory: 3908kb

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: 3620kb

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: 3724kb

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: 3696kb

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: 3ms
memory: 7360kb

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: 6ms
memory: 7360kb

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: 4ms
memory: 7364kb

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: 3660kb

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: 91ms
memory: 7248kb

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: 0ms
memory: 7436kb

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: 7ms
memory: 7260kb

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: 6ms
memory: 7356kb

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: 11ms
memory: 19148kb

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: 7ms
memory: 19316kb

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: 3ms
memory: 19152kb

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: 7ms
memory: 19156kb

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: 20ms
memory: 19248kb

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: 25ms
memory: 19292kb

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: 3ms
memory: 19220kb

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: 48ms
memory: 19176kb

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: 82ms
memory: 19316kb

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: 0ms
memory: 19240kb

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: 74ms
memory: 38952kb

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: 18ms
memory: 38980kb

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: 13ms
memory: 38972kb

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: 187ms
memory: 102200kb

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: 177ms
memory: 102144kb

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: 104ms
memory: 102184kb

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: 90ms
memory: 101860kb

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: 176ms
memory: 102208kb

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: 175ms
memory: 102084kb

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: 525ms
memory: 102128kb

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: 527ms
memory: 102044kb

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: 23ms
memory: 101792kb

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: 31ms
memory: 101876kb

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: 34ms
memory: 101792kb

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: 26ms
memory: 101800kb

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: 58ms
memory: 101872kb

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: 60ms
memory: 101880kb

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: 28ms
memory: 101772kb

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: 27ms
memory: 101952kb

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: 29ms
memory: 101776kb

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: 8ms
memory: 101852kb

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: 3820kb

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: 3560kb

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: 0ms
memory: 3556kb

input:

1 0

output:

0

result:

ok answer is '0'

Test #51:

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

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: 3852kb

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: 3560kb

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: 3632kb

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: 3572kb

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: 3828kb

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: 0ms
memory: 19156kb

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: 0ms
memory: 16548kb

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: 12540kb

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: 0ms
memory: 11572kb

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: 13152kb

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: 7632kb

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: 0ms
memory: 3756kb

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: 0ms
memory: 17572kb

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: 92ms
memory: 3672kb

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: 92ms
memory: 3736kb

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: 78ms
memory: 3856kb

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: 60ms
memory: 4528kb

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: 3ms
memory: 19144kb

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: 0ms
memory: 10004kb

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: 0ms
memory: 18132kb

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: 4368kb

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: 4632kb

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: 3752kb

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: 3880kb

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: 3ms
memory: 19204kb

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: 6ms
memory: 19308kb

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: 0ms
memory: 15188kb

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: 3ms
memory: 16608kb

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: 0ms
memory: 15788kb

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: 3ms
memory: 17120kb

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: 0ms
memory: 19308kb

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: 7ms
memory: 14212kb

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: 6ms
memory: 15796kb

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: 0ms
memory: 16552kb

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: 16796kb

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: 0ms
memory: 16784kb

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: 3ms
memory: 17624kb

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: 3564kb

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: 3820kb

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: 3852kb

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: 3560kb

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: 3628kb

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: 3556kb

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: 3628kb

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: 3828kb

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: 3836kb

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: 0ms
memory: 3544kb

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: 3592kb

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: 0ms
memory: 3452kb

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: 3668kb

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: 39ms
memory: 5432kb

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: 3ms
memory: 11000kb

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: 4ms
memory: 12568kb

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: 0ms
memory: 9212kb

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: 0ms
memory: 17832kb

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: 6ms
memory: 17572kb

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: 9712kb

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: 0ms
memory: 14660kb

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: 0ms
memory: 15552kb

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: 0ms
memory: 11052kb

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: 7ms
memory: 19244kb

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: 3788kb

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: 3788kb

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: 3624kb

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: 3560kb

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: 3524kb

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: 3660kb

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: 3632kb

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: 3556kb

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: 0
Accepted
time: 1971ms
memory: 4532kb

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:

2

result:

ok answer is '2'

Test #122:

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

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
21 23 1
21 24 1
21 25 1
21 26 1
21 27 1
21 28 1
21 29 1
21 30 1
21 31 1
21 32 1
21 33 1
21 34 1
21 35 1
21 36 1
21 37 1
21 38 1
21 39 1
21 ...

output:

2

result:

ok answer is '2'

Test #123:

score: 0
Accepted
time: 381ms
memory: 4532kb

input:

500 9619
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
20 22 1
20 23 1
20 24 1
20 25 1
20 26 1
20 27 1
20 28 1
20 29 1
20 30 1
20 31 1
20 32 1
20 33 1
20 34 1
20 35 1
20 36 1
20 37 1
20 38 1
20 39 1
20 4...

output:

2

result:

ok answer is '2'

Test #124:

score: 0
Accepted
time: 1978ms
memory: 4304kb

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:

1

result:

ok answer is '1'

Test #125:

score: 0
Accepted
time: 431ms
memory: 4504kb

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
21 23 1
21 24 1
21 25 1
21 26 1
21 27 1
21 28 1
21 29 1
21 30 1
21 31 1
21 32 1
21 33 1
21 34 1
21 35 1
21 36 1
21 37 1
21 38 1
21 39 1
21 ...

output:

1

result:

ok answer is '1'

Test #126:

score: 0
Accepted
time: 398ms
memory: 4528kb

input:

500 9619
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
20 22 1
20 23 1
20 24 1
20 25 1
20 26 1
20 27 1
20 28 1
20 29 1
20 30 1
20 31 1
20 32 1
20 33 1
20 34 1
20 35 1
20 36 1
20 37 1
20 38 1
20 39 1
20 4...

output:

1

result:

ok answer is '1'

Test #127:

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

input:

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

output:

1000000000

result:

ok answer is '1000000000'

Test #128:

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

input:

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

output:

1000000000

result:

ok answer is '1000000000'

Test #129:

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

input:

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

output:

1000000000

result:

ok answer is '1000000000'

Test #130:

score: 0
Accepted
time: 1275ms
memory: 28472kb

input:

2500 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:

2

result:

ok answer is '2'

Test #131:

score: 0
Accepted
time: 287ms
memory: 28160kb

input:

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

output:

2

result:

ok answer is '2'

Test #132:

score: 0
Accepted
time: 276ms
memory: 28168kb

input:

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

output:

2

result:

ok answer is '2'

Test #133:

score: 0
Accepted
time: 1271ms
memory: 28388kb

input:

2500 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:

1

result:

ok answer is '1'

Test #134:

score: 0
Accepted
time: 298ms
memory: 28268kb

input:

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

output:

1

result:

ok answer is '1'

Test #135:

score: 0
Accepted
time: 300ms
memory: 28264kb

input:

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

output:

1

result:

ok answer is '1'

Test #136:

score: 0
Accepted
time: 1277ms
memory: 28460kb

input:

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

output:

1000000000

result:

ok answer is '1000000000'

Test #137:

score: 0
Accepted
time: 292ms
memory: 28268kb

input:

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

output:

1000000000

result:

ok answer is '1000000000'

Test #138:

score: 0
Accepted
time: 292ms
memory: 28296kb

input:

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

output:

1000000000

result:

ok answer is '1000000000'

Test #139:

score: 0
Accepted
time: 531ms
memory: 102296kb

input:

5000 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:

2

result:

ok answer is '2'

Test #140:

score: 0
Accepted
time: 256ms
memory: 102216kb

input:

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

output:

2

result:

ok answer is '2'

Test #141:

score: 0
Accepted
time: 244ms
memory: 102096kb

input:

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

output:

2

result:

ok answer is '2'

Test #142:

score: 0
Accepted
time: 500ms
memory: 102400kb

input:

5000 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:

1

result:

ok answer is '1'

Test #143:

score: 0
Accepted
time: 264ms
memory: 102208kb

input:

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

output:

1

result:

ok answer is '1'

Test #144:

score: 0
Accepted
time: 252ms
memory: 102188kb

input:

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

output:

1

result:

ok answer is '1'

Test #145:

score: 0
Accepted
time: 542ms
memory: 102320kb

input:

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

output:

1000000000

result:

ok answer is '1000000000'

Test #146:

score: 0
Accepted
time: 256ms
memory: 102004kb

input:

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

output:

1000000000

result:

ok answer is '1000000000'

Test #147:

score: 0
Accepted
time: 264ms
memory: 102208kb

input:

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

output:

1000000000

result:

ok answer is '1000000000'

Test #148:

score: -100
Time Limit Exceeded

input:

200 10000
119 86 672491811
46 52 472434721
161 7 876933159
42 1 262893335
24 53 183796335
170 11 950710909
83 38 878865861
41 104 919262743
40 31 291578575
126 156 331556293
96 70 465502515
149 7 458584299
196 152 867766341
179 62 279318343
96 6 310202717
124 58 255282771
8 54 885860667
91 3 6345549...

output:


result: