<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

185. Two shortest
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard input
output: standard output



Yesterday Vasya and Petya quarreled badly, and now they don't want to see each other on their way to school. The problem is that they live in one and the same house, leave the house at the same time and go at the same speed by the shortest road. Neither of them wants to change their principles, that is why they want to find two separate shortest routes, which won't make them go along one road, but still they can meet at any junction. They ask you to help them. They number all the junctions with numbers from 1 to N (home and school are also considered as junctions). So their house has the number 1 and the school has the number N, each road connects two junctions exactly, and there cannot be several roads between any two junctions.

Input
The first line contains two integer numbers N and M (2<=N<=400), where M is the number of roads Petya and Vasya noticed. Each of the following M lines contains 3 integers: X, Y and L (1<=X, Y<=N, 1<=L<=10000), where X and Y - numbers of junctions, connected by the road and L is the length of the road.

Output
Write to the first line numbers of the junctions in the way they passed them on the first route. Write to the second line numbers of the junctions in the way they passed them on the second route. If it is impossible to help guys, then output "No solution".

Sample test(s)

Input
6 8
1 2 1
3 2 1
3 4 1
1 3 2
4 2 2
4 5 1
5 6 1
4 6 2

Output
1 3 4 5 6
1 2 4 6
Author:	Andrew V. Lazarev
Resource:	ACM International Collegiate Programming Contest 2003-2004
North-Eastern European Region, Southern Subregion
Date:	2003 October, 9

<|response|>
1. Abridged problem statement  
Given an undirected weighted graph with N nodes (1…N) and M edges. Find two paths from node 1 to node N such that:  
- Each path has length equal to the shortest‐path distance D from 1 to N.  
- The two paths are edge‐disjoint (they may share vertices but no edge).  
If no such pair exists, output “No solution”. Otherwise print each path as a sequence of node numbers.

2. Key observations  
- A single‐source shortest‐path computation (e.g. Dijkstra) from node 1 yields for each node u its distance dist[u] to the source.  
- An undirected edge (u,v,w) lies on some shortest path 1→…→N exactly when dist[u]+w = dist[v] or dist[v]+w = dist[u]. If you orient such edges in increasing‐distance direction, you build a directed acyclic “shortest‐path DAG” containing exactly the edges that participate in at least one shortest path.  
- In that DAG, any path from 1 to N has length D. We now need two edge‐disjoint directed paths in this DAG.  
- Finding k edge‐disjoint paths in a directed graph reduces to a max‐flow problem with unit capacities on each edge. Here k=2.  
- After computing a max‐flow of value two, you can trace two flow‐units from source to sink to recover the two paths.

3. Full solution approach  
a. Run Dijkstra from node 1 to compute dist[1..N], where dist[v] is the distance of a shortest path 1→v. Let D = dist[N].  
b. Build the shortest‐path DAG of size N: for each undirected edge (u,v,w),  
   - if dist[u]+w == dist[v], add directed edge u→v,  
   - if dist[v]+w == dist[u], add directed edge v→u.  
c. Construct a flow network to enforce edge‐disjointness:  
   - Give each original DAG edge e an index i.  
   - Introduce a new “edge‐node” Ei for each i.  
   - Add a unit‐capacity arc u→Ei and Ei→v whenever DAG has u→v with edge‐index i.  
   - The flow network has N + (#DAG edges) nodes; source = 1, sink = N.  
d. Run a unit‐capacity max‐flow (Dinic or Edmonds–Karp) from 1 to N, stopping early if flow≥2.  
   - If the maximum flow < 2, print “No solution” and exit.  
e. Otherwise flow = 2. To extract the two edge‐disjoint paths, do the following twice:  
   - Start at u = 1, walk to N by always following an outgoing arc (u→Ei or Ei→v) that carries 1 unit of flow, decrementing the flow on that arc as you go.  
   - Every time you traverse Ei, record the corresponding original edge u→v to recover the node sequence.  
f. Print the two recovered paths in 1‐based node numbering.

4. C++ implementation with detailed comments  

```cpp
#include <bits/stdc++.h>
// #include <coding_library/graph/maxflow.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

template<class T>
class MaxFlow {
  private:
    struct Edge {
        T flow, cap;
        int idx, rev, to;
        Edge(int _to, int _rev, T _flow, T _cap, int _idx)
            : to(_to), rev(_rev), flow(_flow), cap(_cap), idx(_idx) {}
    };

    vector<int> dist, po;
    int n;

    bool bfs(int s, int t) {
        fill(dist.begin(), dist.end(), -1);
        fill(po.begin(), po.end(), 0);

        queue<int> q;
        q.push(s);
        dist[s] = 0;

        while(!q.empty()) {
            int u = q.front();
            q.pop();

            for(Edge e: adj[u]) {
                if(dist[e.to] == -1 && e.flow < e.cap) {
                    dist[e.to] = dist[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return dist[t] != -1;
    }

    T dfs(int u, int t, T fl = INF) {
        if(u == t) {
            return fl;
        }

        for(; po[u] < (int)adj[u].size(); po[u]++) {
            auto& e = adj[u][po[u]];
            if(dist[e.to] == dist[u] + 1 && e.flow < e.cap) {
                T f = dfs(e.to, t, min(fl, e.cap - e.flow));
                e.flow += f;
                adj[e.to][e.rev].flow -= f;
                if(f > 0) {
                    return f;
                }
            }
        }

        return 0;
    }

  public:
    const static T INF = numeric_limits<T>::max();

    MaxFlow(int n = 0) { init(n); }

    vector<vector<Edge>> adj;

    void init(int _n) {
        n = _n;
        adj.assign(n + 1, {});
        dist.resize(n + 1);
        po.resize(n + 1);
    }

    void add_edge(int u, int v, T w, int idx = -1) {
        adj[u].push_back(Edge(v, adj[v].size(), 0, w, idx));
        adj[v].push_back(Edge(u, adj[u].size() - 1, 0, 0, -1));
    }

    T flow(int s, int t, int max_add = INF) {
        assert(s != t);

        T ret = 0, to_add;
        while(bfs(s, t)) {
            while((to_add = dfs(s, t))) {
                ret += to_add;
                if(ret >= max_add) {
                    return ret;
                }
            }
        }

        return ret;
    }
};

struct Edge {
    int u, v, w;
    Edge() : u(0), v(0), w(0) {}
    Edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}
};

int n, m;
vector<Edge> edges;
vector<vector<pair<int, int>>> adj;

void read() {
    cin >> n >> m;
    edges.resize(m);
    adj.assign(n, {});
    for(int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        edges[i].u--;
        edges[i].v--;
        adj[edges[i].u].emplace_back(edges[i].v, i);
        adj[edges[i].v].emplace_back(edges[i].u, i);
    }
}

vector<vector<pair<int, int>>> get_shortest_path_dag(int src) {
    vector<int> dist(n, numeric_limits<int>::max());
    priority_queue<
        pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>
        pq;

    dist[src] = 0;
    pq.push({0, src});

    while(!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if(d > dist[u]) {
            continue;
        }

        for(auto [v, idx]: adj[u]) {
            if(dist[v] > d + edges[idx].w) {
                dist[v] = d + edges[idx].w;
                pq.push({dist[v], v});
            }
        }
    }

    vector<vector<pair<int, int>>> ret(n);
    for(int i = 0; i < m; i++) {
        if(dist[edges[i].u] + edges[i].w == dist[edges[i].v]) {
            ret[edges[i].u].emplace_back(edges[i].v, i);
        }
        if(dist[edges[i].v] + edges[i].w == dist[edges[i].u]) {
            ret[edges[i].v].emplace_back(edges[i].u, i);
        }
    }

    return ret;
}

void solve() {
    // We need two shortest 1->N paths that share no road (vertices may be
    // reused). Run Dijkstra from node 0 and keep only edges lying on some
    // shortest path, oriented along increasing distance; this shortest-path DAG
    // contains every road usable in a shortest route. Finding two edge-disjoint
    // shortest paths is then a unit-capacity max flow of value 2 on this DAG.
    // We split each road into an intermediate node with capacity 1 (node n + i
    // between its endpoints) so an edge can be used at most once, push flow from
    // 0 to N-1 capped at 2, and if it reaches 2 we reconstruct the two routes
    // by walking the saturated edges greedily.

    vector<vector<pair<int, int>>> dag = get_shortest_path_dag(0);
    MaxFlow<int> mf(n + m);

    for(int i = 0; i < n; i++) {
        for(auto [v, idx]: dag[i]) {
            mf.add_edge(i, n + idx, 1);
            mf.add_edge(n + idx, v, 1, idx);
        }
    }

    if(mf.flow(0, n - 1, 2) < 2) {
        cout << "No solution\n";
        return;
    }

    vector<vector<int>> final_graph(n);

    for(int i = n; i < n + m; i++) {
        for(auto& e: mf.adj[i]) {
            if(e.idx != -1 && e.flow > 0) {
                auto& edge = edges[e.idx];
                int u = edge.u, v = edge.v;
                if(u == e.to) {
                    swap(u, v);
                }
                final_graph[u].push_back(v);
            }
        }
    }

    for(int cnt = 0; cnt < 2; cnt++) {
        vector<int> path = {0};
        int u = 0;

        while(u != n - 1) {
            assert(!final_graph[u].empty());
            int v = final_graph[u].back();
            final_graph[u].pop_back();
            path.push_back(v);
            u = v;
        }

        for(int u: path) {
            cout << u + 1 << ' ';
        }
        cout << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation with detailed comments  
```python
import sys
import threading
def main():
    import heapq
    data = sys.stdin.read().split()
    it = iter(data)
    N, M = int(next(it)), int(next(it))
    edges = []
    adj = [[] for _ in range(N+1)]
    for i in range(M):
        u, v, w = int(next(it)), int(next(it)), int(next(it))
        edges.append((u,v,w))
        adj[u].append((v,i))
        adj[v].append((u,i))

    # 1) Dijkstra from 1
    INF = 10**18
    dist = [INF]*(N+1)
    dist[1] = 0
    pq = [(0,1)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, idx in adj[u]:
            nd = d + edges[idx][2]
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    if dist[N] == INF:
        print("No solution")
        return

    # 2) Build shortest‐path DAG edges
    dag = []  # list of (u,v)
    for i, (u,v,w) in enumerate(edges):
        if dist[u] + w == dist[v]:
            dag.append((u,v))
        if dist[v] + w == dist[u]:
            dag.append((v,u))

    E = len(dag)
    # 3) Build flow network with unit capacities
    # Nodes: 1..N = original; N+1..N+E = edge‐nodes
    size = N + E + 1
    graph = [[] for _ in range(size)]
    # edge structure: to, capacity, rev‐index
    class Edge:
        __slots__ = ('to','cap','rev')
        def __init__(self,to,cap,rev):
            self.to, self.cap, self.rev = to,cap,rev

    def add_edge(u,v,cap):
        graph[u].append(Edge(v,cap,len(graph[v])))
        graph[v].append(Edge(u,0,len(graph[u])-1))

    S, T = 1, N
    for i, (u,v) in enumerate(dag):
        en = N + 1 + i
        add_edge(u, en, 1)
        add_edge(en, v, 1)

    # Dinic
    level = [0]*size
    ptr = [0]*size

    def bfs():
        for i in range(size):
            level[i] = -1
        queue = [S]
        level[S] = 0
        for u in queue:
            for e in graph[u]:
                if level[e.to] < 0 and e.cap > 0:
                    level[e.to] = level[u] + 1
                    queue.append(e.to)
        return level[T] >= 0

    def dfs(u, pushed):
        if u == T or pushed == 0:
            return pushed
        while ptr[u] < len(graph[u]):
            e = graph[u][ptr[u]]
            if level[e.to] == level[u] + 1 and e.cap > 0:
                tr = dfs(e.to, min(pushed, e.cap))
                if tr > 0:
                    e.cap -= tr
                    graph[e.to][e.rev].cap += tr
                    return tr
            ptr[u] += 1
        return 0

    # 4) max‐flow up to 2
    flow = 0
    while flow < 2 and bfs():
        ptr = [0]*size
        while flow < 2:
            pushed = dfs(S, 2-flow)
            if pushed == 0: break
            flow += pushed

    if flow < 2:
        print("No solution")
        return

    # 5) Extract used DAG edges
    used = [[] for _ in range(N+1)]
    for i in range(E):
        en = N + 1 + i
        # any backward capacity >0 implies forward was used
        for e in graph[en]:
            if 1 <= e.to <= N and e.cap > 0:
                u,v = dag[i]
                used[u].append(v)

    # 6) Recover two paths
    for _ in range(2):
        path = [1]
        u = 1
        while u != N:
            v = used[u].pop()
            path.append(v)
            u = v
        print(" ".join(map(str, path)))

if __name__ == "__main__":
    main()
```
