oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

pokewar Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

pokewar.html

The Pokémon Mewtwo was created in a lab from the DNA of Mew. However, it was angry that it is merely a clone and displeased with the concept of being nothing more than a mere lab experiment. Hence, Mewtwo gathered an army of clones to take over the PokéWorld in an epic battle.

PokéTrainer Little Joseph knows he must try to do his best to delay the clones reaching the frontlines so that Ash, Misty and Brock can be more prepared for the PokéWar. Looking at his Electrode, he knows that the Electrode can self-destruct and destroy one edge in the path of the enemy.

The frontline is marked as node N and where the clone army is now is marked as node 1.

Mewtwo is very smart and can lead his clone army by taking the shortest path possible.

Your task as a PokéProgrammer is to find the best place to put the Electrode, such that the Enemy's fastest possible route after the bombing slowed down as much as possible.

Input

The first line of input contains the 2 integers N and E.

The next E lines of input each contain 3 integers, A, B, W. This means that there is a road between nodes A and B which takes W time to travel.

For each test case, 0 < W ≤ 1,000 and 0 < N ≤ 500.

Output

Print out the time it will take for the Enemy to move supplies from the base to the frontlines, after the optimal bombing. Print -1 if after you place the bomb there is no route from the base to the frontlines.

Sample Input 1

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

Sample Output 1

10

Tags

Graph Theory, ToFixStatement

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110081s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o pokewar -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.