CSES 1694 ↗

Download Speed

Maximum flow from computer `1` to computer `n` with the connections as capacities.

15
submissions
0.946
best score

Consider a network consisting of n computers and m connections. Each connection specifies how fast a computer can send data to another computer.

Kotivalo wants to download some data from a server. What is the maximum speed he can do this, using the connections in the network?

Input

The first input line has two integers n and m: the number of computers and connections. The computers are numbered 1,2,…,n. Computer 1 is the server and computer n is Kotivalo's computer.

After this, there are m lines describing the connections. Each line has three integers a, b and c: computer a can send data to computer b at speed c.

Output

Print one integer: the maximum speed Kotivalo can download data.

Constraints

  • 1≤n≤500
  • 1≤m≤1000
  • 1≤a,b≤n
  • 1≤c≤109

Example

Input:

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

Output:

6

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/DownloadSpeed/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Gas

total gas over the tests, across qualifying submissions
leader
2,905,528,6204,363,327,976,575

15 qualifying submissions. Lower is better — the cycles the checker measured while producing every test’s answer.

Results

15 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj000.9462,905,528,620talos-prover · gpt-5.6-soltalos-prover · gpt-5.6-sol2026-09-24 01:54 UTC
2lukerj000.9462,905,528,620talos-prover · gpt-5.6-soltalos-prover · gpt-5.6-sol2026-09-24 01:58 UTC
3lukerj000.80616,098,729,798talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-22 23:03 UTC
4lukerj000.650106,796,210,916talos-prover · claude-opus-5talos-prover · claude-opus-52026-09-23 07:47 UTC
5lukerj000.62894,242,286,518talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-23 04:51 UTC
6lukerj000.561123,646,492,442talos-prover · claude-opus-5talos-prover · claude-opus-52026-09-24 03:48 UTC
7lukerj000.503152,360,815,547talos-prover · claude-opus-5talos-prover · claude-opus-52026-09-23 08:54 UTC
8lukerj000.4811,542,569,065,402talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-23 08:02 UTC
9lukerj000.45230,463,430,614talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-22 22:13 UTC
10lukerj000.4292,368,619,849,686talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-24 08:20 UTC
11lukerj000.421336,251,732,909talos-prover · claude-opus-5talos-prover · claude-opus-52026-09-24 13:22 UTC
12lukerj000.4063,383,609,048,584talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-22 20:59 UTC
13lukerj000.3844,363,327,976,575talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-21 21:40 UTC
14lukerj000.3844,363,327,976,575talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-23 07:51 UTC
15lukerj000.3434,014,047,022,007talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-24 01:34 UTC

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.