1. Abridged Problem Statement  
Given an undirected weighted graph with N junctions (nodes) and M roads (edges), find two edge-disjoint paths from node 1 to node N such that both paths have the minimum possible total length (i.e., both are shortest paths). Paths may share vertices but must not share any edge. If no such pair exists, output "No solution". Otherwise, print the two sequences of junction indices.

2. Detailed Editorial  

Overview  
We need two distinct shortest routes (by total length) from source 1 to sink N, sharing no edge. This is the two-edge-disjoint-paths problem on a weighted graph, but with the extra constraint that each path individually must have length equal to the graph's shortest-path distance D.

Steps  
1. Compute single-source shortest-path distances dist[u] from node 1 to every node using Dijkstra (O(M log N)).  
2. Build the "shortest-path DAG": 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 v->u. This DAG contains exactly all edges that lie on at least one shortest path from 1.  
3. On this DAG, we want two edge-disjoint paths from 1 to N. Reduce to a unit-capacity max-flow problem:  
   a. Create a flow network with vertex set {0...N-1} together with one extra node per DAG edge.  
   b. For each DAG edge u->v corresponding to input edge index i, add two directed arcs:  
      - u -> (N + i) with capacity 1  
      - (N + i) -> v with capacity 1 and store i as an "idx".  
   This construction ensures that any flow of value k corresponds to k paths each using distinct original edges, since each edge-node N+i has unit capacity.  
4. Run Dinic's max-flow from source=0 to sink=N-1 with early exit once flow >= 2. If max-flow < 2, print "No solution". Otherwise flow=2.  
5. Extract the two paths: traverse the flow graph, starting at 0, repeatedly following an outgoing arc that carries flow to a neighbor, decrementing that flow, until you reach N-1. Do this twice to recover two edge-disjoint sequences of nodes.  
6. Output the two paths (converting back to 1-based indices).

Complexity  
Dijkstra: O(M log N). Building DAG & network: O(N + M). Dinic on unit capacities with small flow (2): very fast for N<=400. Path extraction: O(N) twice.

3. C++ Solution

```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;
}
```

4. Python Solution

```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()
```

5. Compressed Editorial  
- Run Dijkstra from node 1 to get dist[].  
- Build a directed acyclic "shortest-path DAG" containing only edges on some shortest path.  
- Transform each DAG edge into a little gadget (node with two unit-cap edges) in a flow network of size N+M.  
- Max-flow (Dinic) from 1 to N, capacity=1 per edge, stop once flow>=2.  
- If max-flow<2 -> no solution. Otherwise, extract the two unit-flows as two edge-disjoint shortest paths.
