### 2012 Canadian Computing Competition, Stage 2

## Day 1, Problem 2: The Hungary Games

Welcome to the Hungary Games! The streets of Budapest form a twisted network of one-way
streets. You have been forced to join a race as part of a "Reality TV" show where you race
through these streets, starting at the Széchenyi thermal bath (`s` for
short) and ending at the Tomb of Gül Baba (`t` for short).

Naturally, you want to complete the race as quickly as possible, because you will get
more promotional contracts the better you perform. However, there is a catch: any person
who is smart enough to take a shortest `s`-`t` route will be thrown into
the Pálvölgyi cave system and kept as a national treasure. You would like to
avoid this fate, but still be as fast as possible. Write a program that computes a
strictly-second-shortest `s`-`t` route.

Sometimes the strictly-second-shortest route visists some nodes more than once; see Sample Input 2 for an example.

### Input Format

The first line will have the format `N` `M`, where
`N` is the number of nodes in Budapest and `M` is the number of
edges. The nodes are 1, 2, ..., `N`; node 1 represents
`s`; node `N` represents `t`. Then there are
`M` lines of the form `A` `B` `L`, indicating
a one-way street from `A` to `B` of length `L`. You can
assume that `A` ≠ `B` on these lines, and that the ordered
pairs (`A`, `B`) are distinct.

### Output Format

Output the length of a strictly-second-shortest route from `s` to
`t`. If there are less than two possible lengths for routes from `s` to
`t`, output -1.

### Limits

Every length `L` will be a positive integer between 1 and 10000. For
50% of the test cases, we will have 2 ≤ N ≤ 40 and
0 ≤ M ≤ 1000. All test cases will have
2 ≤ N ≤ 20000 and 0 ≤ M ≤ 100000.

### Sample Input 1

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

### Sample Output 1

11

### Explanation

There are two shortest routes of length 10 (1 → 2 → 4, 1 → 3 → 4) and the strictly-second shortest route is 1 → 2 → 3 →4 with length 11.

### Sample Input 2

2 2 1 2 1 2 1 1

### Sample Output 2

3

### Explanation

The shortest route is 1 → 2 of length 1, and the strictly-second route is 1 → 2 → 1 → 2 of length 3.

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 64M

**Added:** Jun 20, 2012

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, TEXT, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...