There and Back Again (Problem J, The 2024 ICPC Asia Pacific Championship, 2024)
Time limit: 2 sec
Author: Peter Rossmanith

# Problem Statement

There are $n$ cities in Asia-Pacific, numbered from $1$ to $n$. The 2024 ICPC Asia Pacific Championship is held in Hanoi, which is city $n$.

There are $m$ bidirectional roads, numbered from $1$ to $m$, connecting some pairs of cities. Road $i$ connects cities $u_i$ and $v_i$ and takes $t_i$ units of time to travel in either direction. Each road connects different cities and different roads connect different pairs of cities.

You live in city $1$. You would like to travel to city $n$ to attend the contest through a sequence of roads, and then travel back to city $1$ through a sequence of roads. Traveling through the same route is boring, so you would like the routes in both traversals to be different. Two routes are considered different if the **set of distinct** roads traversed through one route is different from the **set of distinct** roads traversed through the other route.

In each traversal, it is possible to pass through the same city or road multiple times. It is also possible to continue traversing after reaching the destination city (i.e., city $1$ or city $n$). The *traversal time* is the sum of the travel times of the roads passed through in the traversal. If a road is passed through multiple times in the traversal, then the travel time of the road is also counted multiple times accordingly.

Determine the minimum total traversal time to do both traversals satisfying the requirements above, or indicate if the requirements cannot be satisfied.

# Input

The first line of input contains two integers $n$ and $m$ ($2 \le n \le 100\,000$; $1 \le m \le \min(\frac{n(n-1)}{2},\,300\,000)$). Each of the next $m$ lines contains three integers. The $i$-th line contains $u_i$, $v_i$, and $t_i$ ($1 \le u_i < v_i \le n$; $1 \le t_i \le 1000$). Different roads connect different pairs of cities.

# Output

Output an integer representing the minimum total traversal time to do both traversals satisfying the requirements above, or $-1$ if the requirements cannot be satisfied.

# Sample Input #1
```
3 2
1 2 10
1 3 5
```
# Sample Output #1
```
30
```
### Explanation for the sample input/output #1

The cities and roads are illustrated by Figure J.1.

![Figure J.1: Illustration of sample input #1.](icpc-apac-2024-back-1.png)

One possible way to minimize the total traversal time is as follows:

- Travel from city 1 to city 3 by passing through road 2 (connecting cities 1 and 3). The traversal time is 5. The set of traversed roads is {2}.
- Travel from city 3 to city 1 by passing through road 2, and then road 1 (connecting cities 1 and 2) twice. The traversal time is 5 + 10 + 10 = 25. The set of traversed roads is {1, 2}.

It can be shown that there is no way to do both traversals with a smaller total traversal time.

# Sample Input #2
```
4 3
1 2 10
2 3 5
3 4 2
```
# Sample Output #2
```
-1
```
### Explanation for the sample input/output #2

The cities and roads are illustrated by Figure J.2.

![Figure J.2: Illustration of sample input #2.](icpc-apac-2024-back-2.png)

To go from city 1 to city 4 and then back, both traversals have to pass through all the roads. Therefore, it is impossible to satisfy the requirements above.

# Sample Input #3
```
4 4
1 2 3
2 4 2
1 3 3
3 4 4
```
# Sample Output #3
```
12
```
# Sample Input #4
```
3 1
1 2 1000
```
# Sample Output #4
```
-1
```

Sample inputs:
3 2
1 2 10
1 3 5

4 3
1 2 10
2 3 5
3 4 2

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

3 1
1 2 1000

Sample outputs:
30

-1

12

-1

# Solution Analysis
Analysis author: Jonathan Irvin Gunawan

We would like to compute the sum of the route that has the minimum total traversal time (the best route) and the route that has the second minimum total traversal time (the second best route). Finding the best route can be done with Dijkstra algorithm. We can also note the set of roads traversed in this route.

To find the second best route, we run Dijkstra algorithm twice to compute, for each city $u$, the shortest path to city $1$ (denoted as $S_u$) and the shortest path to city $n$ (denoted as $T_u$). We then iterate each road that is not traversed in either direction in the best route to try which edge is traversed in the second best route. For each such road $(u,v)$, the minimum total traversal time for the second best route by traversing this edge is  
$S_u + w(u,v) + T_v$  
where $w(u,v)$ is the time it takes to traverse the road. We then take the minimum value among all such roads.

This solution runs in $O(n \log n)$ time.

Special judge (C++ scorer):
/**
 * Default validator from https://github.com/Kattis/problemtools
 * Modified (as small as possible) to tcframe format by jonathanirvings.
 */

#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>

std::ifstream judgein, judgeans, conans;
FILE *judgemessage = NULL;
FILE *diffpos = NULL;
int judgeans_pos, con_pos;
int judgeans_line, con_line;

void ac() {
  puts("AC");
  exit(0); 
}

void wa() {
  puts("WA");
  exit(0);
}

void wrong_answer(const char *err, ...) {
  wa();
}

void judge_error(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  // If judgemessage hasn't been set up yet, write error to stderr
  if (!judgemessage) judgemessage = stderr;
  vfprintf(judgemessage, err, pvar);
  fprintf(judgemessage, "\n");
  assert(!"Judge Error");
}

bool isfloat(const char *s, double &val) {
  char trash[20];
  double v;
  if (sscanf(s, "%lf%10s", &v, trash) != 1) return false;
  val = v;
  return true;
}

template <typename Stream>
void openfile(Stream &stream, const char *file, const char *whoami) {
  stream.open(file);
  if (stream.fail()) {
    judge_error("%s: failed to open %s\n", whoami, file);
  }
}

FILE *openfeedback(const char *feedbackdir, const char *feedback, const char *whoami) {
  std::string path = std::string(feedbackdir) + "/" + std::string(feedback);
  FILE *res = fopen(path.c_str(), "w");
  if (!res) {
    judge_error("%s: failed to open %s for writing", whoami, path.c_str());
  }
  return res;
}

const char *USAGE = "Usage: %s judge_in judge_ans contestant_ans";

int main(int argc, char **argv) {
  if(argc < 4) {
    judge_error(USAGE, argv[0]);
  }
  openfile(judgein, argv[1], argv[0]);
  openfile(judgeans, argv[2], argv[0]);
  openfile(conans, argv[3], argv[0]);

  bool case_sensitive = false;
  bool space_change_sensitive = false;
  bool use_floats = false;
  double float_abs_tol = -1;
  double float_rel_tol = -1;

  for (int a = 4; a < argc; ++a) {
    if        (!strcmp(argv[a], "case_sensitive")) {
      case_sensitive = true;
    } else if (!strcmp(argv[a], "space_change_sensitive")) {
      space_change_sensitive = true;
    } else if (!strcmp(argv[a], "float_absolute_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_abs_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_relative_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      float_abs_tol = float_rel_tol;
      ++a;
    } else {
      judge_error(USAGE, argv[0]);
    }
  }
  use_floats = float_abs_tol >= 0 || float_rel_tol >= 0;

  judgeans_pos = con_pos;
  judgeans_line = con_line = 1;
   
  std::string judge, team;
  char trash[20];
  while (true) {
    // Space!  Can't live with it, can't live without it...
    while (isspace(judgeans.peek())) {
      char c = (char)judgeans.get();
      if (space_change_sensitive) {
        int d = conans.get();
        if (c != d) {
          wrong_answer("Space change error: got %d expected %d", d, c);
        }
        if (d == '\n') ++con_line;
        ++con_pos;
      }
      if (c == '\n') ++judgeans_line;
      ++judgeans_pos;
    }
    while (isspace(conans.peek())) {
      char d = (char)conans.get();
      if (space_change_sensitive) {
        wrong_answer("Space change error: judge out of space, got %d from team", d);
      }
      if (d == '\n') ++con_line;
      ++con_pos;
    }

    if (!(judgeans >> judge))
      break;

    if (!(conans >> team)) {
      wrong_answer("User EOF while judge had more output\n(Next judge token: %s)", judge.c_str());
    }
     
    double jval, tval;
    if (use_floats && isfloat(judge.c_str(), jval)) {
      if (!isfloat(team.c_str(), tval)) {
        wrong_answer("Expected float, got: %s", team.c_str());
      }
      if(!(fabs(jval - tval) <= float_abs_tol) && 
         !(fabs(jval - tval) <= float_rel_tol*fabs(jval))) {
        wrong_answer("Too large difference.\n Judge: %s\n Team: %s\n Difference: %le\n (abs tol %le rel tol %le)", 
               judge.c_str(), team.c_str(), jval-tval, float_abs_tol, float_rel_tol);
      }
    } else if (case_sensitive) {
      if (strcmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    } else {
      if(strcasecmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    }
    judgeans_pos += judge.length();
    con_pos += team.length();
  }

  if (conans >> team) {
    wrong_answer("Trailing output:\n%s", team.c_str());
  }

  ac();
}