<|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.

314. Shortest Paths
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



You are given a graph with one vertex marked as source s and one as destination t. Each edge of the graph has a positive length. Find the shortest path from s to t. Then find the second-shortest path (the shortest one of all the paths from s to t except the one you've just found). Then the third-shortest, and so on. Output the lengths of first k such paths.

Note that these paths may not be simple, i.e. they may contain some vertex or edge several times (see the 2nd example).

Input
The first line of the input file contains n, the number of vertices of the graph, m, the number of edges of the graph, and k, the number of paths sought (2 ≤ n ≤ 10000, 2 ≤ m ≤ 50000, 2 ≤ k ≤ 10000).

The second line of the input file contains s and t (integers between 1 and n, inclusive, s != t).

The next m lines contain the descriptions of the edges, each description consisting of three integer numbers: a b c, denoting the edge from a to b with length c (1 ≤ a,b ≤ n, a != b, 1 ≤ c ≤ 1000). There may be more than one edge for the same a and b.

Output
Output k integer numbers in non-decreasing order — the lengths of the paths. In case there are less than k different paths from s to t, output NO instead of the lengths of all non-existent paths.

Example(s)
sample input
sample output
4 5 5
1 4
1 2 1
2 3 1
3 4 1
1 3 1
2 4 1
2
2
3
NO
NO

sample input
sample output
4 4 5
1 4
1 2 10
2 3 10
3 4 10
3 2 10
30
50
70
90
110

sample input
sample output
2 2 10
1 2
1 2 5
2 1 7
5
17
29
41
53
65
77
89
101
113

<|response|>
1. Abridged Problem Statement  
You have a directed graph with n vertices (1…n) and m positive‐weight edges. Given a source s and destination t, you must output the lengths of the first k shortest s→t paths, allowing repeated vertices/edges. If fewer than k distinct paths exist, output “NO” for each missing one. Paths are reported in nondecreasing order of total length.

2. Key Observations  
- Enumerating k shortest non‐simple paths can be done in O((n+m) log n + k log k) time by Eppstein’s algorithm.  
- First, compute the single‐source shortest distances from every vertex v to t (i.e. dist[v]) by running Dijkstra on the reversed graph.  
- Build a shortest‐path arborescence T rooted at t: for each u pick one outgoing edge u→v such that dist[u] = w(u→v)+dist[v].  
- Every other edge u→v (“non‐tree edge”) represents a one‐edge detour off the unique shortest tree‐path; its extra cost (penalty) is w(u→v)+dist[v]–dist[u]≥0.  
- At each node u collect all penalties of non‐tree edges into a meldable min‐heap H[u]. Melding these heaps up the tree (child into parent) collects all single‐deviation options at s.  
- The best path is simply dist[s]. Subsequent best paths correspond to picking the next cheapest deviation. We maintain a global min‐heap of states (current total length, deviation‐heap). Extract the minimum, record its length, then split its heap state into two sub‐heaps (left/right) and also spawn deviations from the deviation’s endpoint. This systematically enumerates the k smallest‐cost single‐deviation extensions.

3. Full Solution Approach  
Step A – Reverse Dijkstra and tree construction  
  1. Build adjacency lists for the graph and its reverse.  
  2. Run Dijkstra from t on the reversed graph to compute dist[v]=shortest distance v→…→t.  
  3. For each u, scan outgoing edges u→v; the first edge satisfying dist[u]==w+dist[v] is chosen as the “tree edge” from u in T.  

Step B – Collect deviation penalties  
  1. For every u and every outgoing edge u→v not used in T, compute penalty = w(u→v)+dist[v]–dist[u] (≥0).  
  2. Push (penalty, v) into a local meldable min‐heap H[u].  

Step C – Merge heaps up the tree  
  1. Topologically sort T so that children come before parents.  
  2. In reverse topological order, do H[parent] = merge(H[parent], H[child]) for each child.  
  3. After this, H[s] contains all single‐edge deviations off the shortest s→t path.  

Step D – Enumerate k shortest paths  
  1. The 1st shortest path has length dist[s].  
  2. If k>1 and H[s] is not empty, initialize a global min‐heap PQ and push state (dist[s]+H[s].top().penalty, H[s]).  
  3. While PQ is nonempty and we need more paths:  
     a. Pop (currLen, heapState) = PQ.top().  
     b. Record currLen as the next shortest path length.  
     c. Split heapState into (head, leftHeap, rightHeap), where head = (penalty, v).  
        – If leftHeap not empty, push (currLen – head.penalty + leftHeap.top().penalty, leftHeap).  
        – If rightHeap not empty, push analogous state.  
        – Also, if H[v] not empty, push (currLen + H[v].top().penalty, H[v]).  
  4. Fill up to k answers; for any missing, output “NO”.  

Data Structures  
- dist[]: vector of size n.  
- tree_edge[u]: index of the chosen outgoing tree edge, or –1.  
- H[u]: a *persistent* meldable heap of (penalty, v) pairs. We use a randomized mergeable heap supporting O(log N) merge, top, pop, and a persistent copy operation.  
- PQ: global min‐heap of pairs (total_length, heap_state).
4. C++ Solution
```cpp
#include <bits/stdc++.h>

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 = int>
class MeldableHeap {
  private:
    static uint32_t rng() {
        static mt19937 static_rng(random_device{}());
        return static_rng();
    }

    struct Node {
        T key;
        Node *left, *right;

        Node(T _key) : key(_key), left(nullptr), right(nullptr) {}
    };

    Node* merge(Node* a, Node* b) {
        if(!a) {
            return b;
        }
        if(!b) {
            return a;
        }

        if(a->key > b->key) {
            swap(a, b);
        }

        Node* q = new Node(a->key);
        if(rng() & 1) {
            q->left = merge(a->left, b);
            q->right = a->right;
        } else {
            q->left = a->left;
            q->right = merge(a->right, b);
        }

        return q;
    }

    pair<Node*, Node*> pop(Node* a) {
        Node* head = new Node(a->key);
        Node* tail = merge(a->left, a->right);
        return {head, tail};
    }

  public:
    Node* root;

    MeldableHeap() : root(nullptr) {}
    MeldableHeap(Node* _root) : root(_root) {}

    MeldableHeap copy() const {
        MeldableHeap new_heap;
        new_heap.root = root;
        return new_heap;
    }

    MeldableHeap merge(const MeldableHeap<T>& other) {
        MeldableHeap new_heap;
        new_heap.root = merge(root, other.root);
        return new_heap;
    }

    friend MeldableHeap merge(
        const MeldableHeap<T>& a, const MeldableHeap<T>& b
    ) {
        return a.merge(b);
    }

    void push(T key) {
        Node* new_node = new Node(key);
        root = merge(root, new_node);
    }

    T pop() {
        assert(root);
        auto [head, tail] = pop(root);
        root = tail;
        return head->key;
    }

    T top() const { return root->key; }

    tuple<T, MeldableHeap<T>, MeldableHeap<T>> trio() const {
        return {
            root->key, MeldableHeap<T>{root->left}, MeldableHeap<T>{root->right}
        };
    }

    bool empty() const { return root == nullptr; }

    bool operator<(const MeldableHeap<T>& other) const {
        return top() < other.top();
    }
};

template<class T = int>
class EppsteinShortestPaths {
  private:
    const T inf = numeric_limits<T>::max() / 2;

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

    pair<vector<T>, vector<int>> build_dijkstra_tree(int t) {
        vector<T> dist(n, inf);

        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> pq;
        dist[t] = 0;
        pq.emplace(0, t);

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

            for(auto [v, idx]: rev_adj[u]) {
                T nd = d + edges[idx].w;
                if(nd < dist[v]) {
                    dist[v] = nd;
                    pq.emplace(nd, v);
                }
            }
        }

        vector<int> tree(n, -1);
        for(int u = 0; u < n; u++) {
            for(auto [v, idx]: adj[u]) {
                if(dist[u] == dist[v] + edges[idx].w) {
                    tree[u] = idx;
                    break;
                }
            }
        }

        return {dist, tree};
    }

    vector<int> topsort(const vector<int>& tree) {
        vector<int> deg(n, 0);
        for(int u = 0; u < n; u++) {
            if(tree[u] != -1) {
                deg[edges[tree[u]].v]++;
            }
        }

        queue<int> q;
        for(int u = 0; u < n; u++) {
            if(deg[u] == 0) {
                q.push(u);
            }
        }

        vector<int> order;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            order.push_back(u);

            if(tree[u] != -1) {
                int v = edges[tree[u]].v;
                deg[v]--;
                if(deg[v] == 0) {
                    q.push(v);
                }
            }
        }

        return order;
    }

  public:
    int n;
    vector<vector<pair<int, int>>> adj;
    vector<vector<pair<int, int>>> rev_adj;
    vector<Edge> edges;

    void init(int _n) {
        n = _n;
        edges.clear();
        adj.assign(n, {});
        rev_adj.assign(n, {});
    }

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

    int add_edge(int u, int v, T w, bool directed = true) {
        int idx = edges.size();
        edges.emplace_back(u, v, w);
        adj[u].emplace_back(v, idx);
        rev_adj[v].emplace_back(u, idx);

        if(!directed) {
            edges.emplace_back(v, u, w);
            adj[v].emplace_back(u, idx + 1);
            rev_adj[u].emplace_back(v, idx + 1);
        }

        return idx;
    }

    vector<T> get_k_shortest_paths(int s, int t, int k) {
        auto dist_and_tree = build_dijkstra_tree(t);
        auto dist = dist_and_tree.first;
        auto tree = dist_and_tree.second;

        if(dist[s] == inf || k <= 0) {
            return vector<T>();
        }

        vector<MeldableHeap<pair<T, int>>> heaps(n);
        for(int u = 0; u < n; u++) {
            for(auto& [v, idx]: adj[u]) {
                if(tree[u] == idx) {
                    continue;
                }

                T cost = edges[idx].w + dist[v] - dist[u];
                heaps[u].push({cost, v});
            }
        }

        auto order = topsort(tree);
        reverse(order.begin(), order.end());
        for(int u: order) {
            if(tree[u] != -1) {
                int par = edges[tree[u]].v ^ edges[tree[u]].u ^ u;
                heaps[u] = heaps[u].merge(heaps[par]);
            }
        }

        vector<T> ans = {dist[s]};
        if(heaps[s].empty()) {
            return ans;
        }

        priority_queue<
            pair<T, MeldableHeap<pair<T, int>>>,
            vector<pair<T, MeldableHeap<pair<T, int>>>>, greater<>>
            pq;
        pq.emplace(dist[s] + heaps[s].top().first, heaps[s].copy());

        while(!pq.empty() && (int)ans.size() < k) {
            auto [d, meld_heap] = pq.top();
            pq.pop();
            ans.push_back(d);

            auto [head, left_heap, right_heap] = meld_heap.trio();
            if(!left_heap.empty()) {
                pq.emplace(d - head.first + left_heap.top().first, left_heap);
            }
            if(!right_heap.empty()) {
                pq.emplace(d - head.first + right_heap.top().first, right_heap);
            }

            int v = head.second;
            if(!heaps[v].empty()) {
                pq.emplace(d + heaps[v].top().first, heaps[v].copy());
            }
        }

        return ans;
    }
};

int n, m, k, s, t;
EppsteinShortestPaths<int64_t> ksp;

void read() {
    cin >> n >> m;
    cin >> k;
    cin >> s >> t;
    s--;
    t--;

    ksp.init(n);
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        ksp.add_edge(u, v, w);
    }
}

void solve() {
    // The k shortest s-t paths (allowed to repeat vertices/edges) come straight
    // from Eppstein's algorithm, which the EppsteinShortestPaths class
    // implements: build the shortest-path tree toward t, give every non-tree
    // edge a "detour cost" (its sidetrack weight w + dist[v] - dist[u]), and
    // organize the available detours per vertex into persistent meldable heaps
    // inherited down the tree. A path is then encoded by the sequence of
    // sidetrack edges it takes; enumerating these in increasing total cost with
    // a priority queue over heap nodes yields the path lengths in order.
    //
    // We request k lengths and print them; whenever fewer than k distinct paths
    // exist, the remaining positions are filled with NO.

    auto ans = ksp.get_k_shortest_paths(s, t, k);
    for(int i = 0; i < k; i++) {
        if(i < (int)ans.size()) {
            cout << ans[i] << '\n';
        } else {
            cout << "NO\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  
(Note: this Python version is for educational clarity. For the contest constraints, a C++ solution is recommended.)  
```python
import sys, threading, heapq

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n, m, K = int(next(it)), int(next(it)), int(next(it))
    s, t = int(next(it))-1, int(next(it))-1

    # Read graph
    adj  = [[] for _ in range(n)]
    radj = [[] for _ in range(n)]
    edges = []
    for i in range(m):
        u = int(next(it))-1
        v = int(next(it))-1
        w = int(next(it))
        edges.append((u,v,w))
        adj[u].append((v,i))
        radj[v].append((u,i))

    # A) Reverse Dijkstra from t to get dist[v]=min v→...→t
    INF = 10**18
    dist = [INF]*n
    dist[t] = 0
    pq = [(0,t)]
    while pq:
        d, u = heapq.heappop(pq)
        if d>dist[u]: continue
        for (v,ei) in radj[u]:
            nd = d + edges[ei][2]
            if nd<dist[v]:
                dist[v] = nd
                heapq.heappush(pq,(nd,v))

    # If no path from s even for the first, print NOs
    if dist[s] == INF:
        print(*["NO"]*K, sep="\n")
        return

    # B) Build shortest‐path tree: tree_edge[u] = index of chosen outgoing edge
    tree_edge = [-1]*n
    for u in range(n):
        for (v,ei) in adj[u]:
            w = edges[ei][2]
            if dist[u] == w + dist[v]:
                tree_edge[u] = ei
                break

    # C) For each u collect non‐tree edges into a min‐heap H[u]
    H = [[] for _ in range(n)]
    for u in range(n):
        du = dist[u]
        if du==INF: continue
        for (v,ei) in adj[u]:
            if ei == tree_edge[u]: continue
            w = edges[ei][2]
            pen = w + dist[v] - du  # ≥0
            heapq.heappush(H[u], (pen, v))

    # D) Toposort T (children before parents)
    indeg = [0]*n
    for u in range(n):
        ei = tree_edge[u]
        if ei>=0:
            indeg[ edges[ei][1] ] += 1
    q = [u for u in range(n) if indeg[u]==0]
    topo = []
    for u in q:
        topo.append(u)
        ei = tree_edge[u]
        if ei>=0:
            v = edges[ei][1]
            indeg[v] -= 1
            if indeg[v]==0:
                q.append(v)
    # Merge child heaps into parent in reverse order
    for u in reversed(topo):
        ei = tree_edge[u]
        if ei<0: continue
        p = edges[ei][1]
        # small-to-large merge
        if len(H[u]) > len(H[p]):
            H[u], H[p] = H[p], H[u]
        for item in H[u]:
            heapq.heappush(H[p], item)
        H[u].clear()

    # E) Extract k shortest
    ans = [dist[s]]
    # Global min-heap stores (totalLen, nodeID, snapshotOfHeapAsTuple)
    global_pq = []
    if H[s]:
        pen, v = H[s][0]
        global_pq.append((dist[s] + pen, s, tuple(H[s])))
        heapq.heapify(global_pq)

    while global_pq and len(ans)<K:
        curLen, u, snap = heapq.heappop(global_pq)
        ans.append(curLen)
        # Convert snapshot to a list‐heap
        local = list(snap)
        # Pop head
        head = local[0]
        pen, v = head
        # rest of the heap as two splits: left=(1:), right=()
        rest = local[1:]
        # Variant 1: continue with rest
        if rest:
            pen2, _ = rest[0]
            heapq.heappush(global_pq, (curLen - pen + pen2, u, tuple(rest)))
        # Variant 2: deviations at v
        if H[v]:
            pen3, _ = H[v][0]
            heapq.heappush(global_pq, (curLen + pen3, v, tuple(H[v])))

    # Output exactly K lines
    out = []
    for i in range(K):
        if i < len(ans):
            out.append(str(ans[i]))
        else:
            out.append("NO")
    print("\n".join(out))

if __name__=="__main__":
    threading.Thread(target=main).start()
```

Explanation Highlights  
- We compute dist[v] once in O((n+m) log n).  
- The shortest‐path tree T has exactly one path from any u to t of minimal length.  
- Every other edge is a single “detour” whose extra cost we record.  
- By merging all detour‐heaps up to the source, we collect all 1‐edge deviations from the unique shortest s→t path.  
- Extracting the k smallest total lengths is a matter of repeatedly pulling from a global min‐heap of (current_length, heap_state) and splitting that heap state into sub‐options.  
- This yields all k shortest (possibly non‐simple) paths in O((n+m) log n + k log k) time.