## 1) Abridged problem statement

You are given a **directed weighted graph** with `n` vertices and `m` edges (edge `i` has travel time `c[i]`). You must go from start `S` to finish `T`.

Additionally, there are `r` **special routes**, each described as a sequence of edge IDs forming a valid simple path. **Every time your traveled path contains one of these special routes as a contiguous subpath**, you incur an **extra penalty equal to the total time of that special route** (as if you traversed that route twice). If the same special route is listed multiple times, penalties stack.

Find the minimum possible total time from `S` to `T` (base edge costs + all penalties), and output any optimal sequence of edge IDs. If `T` is unreachable, output `-1`.

Constraints highlights:
- Outdegree of each vertex ≤ 10.
- Sum of lengths of all special routes ≤ `2m`.
- Each edge appears in ≤ 10 special routes.

---

## 2) Detailed editorial (how the solution works)

### Key idea: treat the path as a "string" of edge IDs
A walk/path in the graph corresponds to a sequence of edge indices:

  e_1, e_2, …, e_L

Each special route is also a sequence of edge indices (a "pattern"). The penalty rule says:

> If a pattern appears as a **substring** of your edge-sequence, add its pattern-cost once for each occurrence.

Where pattern-cost = sum of base edge weights along that special route.

So the objective becomes:

  minimize ∑ c[e_i]  +  ∑_{occurrences of patterns} (pattern-cost)

This is exactly a classic "string with pattern occurrences" accumulation problem — solved efficiently by **Aho–Corasick automaton**.

---

### Step A: Build Aho–Corasick over patterns (edge IDs as alphabet)
- Alphabet symbols are edge IDs `0..m-1`.
- Insert all `r` special routes as patterns, with an ID `i`.

The automaton state represents the **longest suffix of the processed edge sequence that is also a prefix of some pattern**.

#### Why add singleton patterns `{edge}` with cost 0?
The code inserts `{i}` for every edge `i` with cost 0. This is not strictly required for correctness of costs, but it guarantees the automaton always has a meaningful transition/state for every edge encountered and keeps state-space behavior convenient. (Cost is 0, so it doesn't alter the objective.)

---

### Step B: Precompute penalty added when entering an automaton state
In Aho–Corasick, when you land in a state `u`, patterns that end at `u` (and also at its suffix-link ancestors) are exactly the patterns that end at the current position in the text.

Let:
- `end_cost[u]` = sum of pattern-costs of patterns whose terminal state is exactly `u`.
- `state_cost[u]` = sum of `end_cost[x]` over `x = u, link(u), link(link(u)), ...` up to root.

Then whenever we extend the path with an edge and transition to `new_state`, the additional penalty incurred **at that step** is exactly `state_cost[new_state]`, because it sums all patterns that just ended here.

The code computes `state_cost` in a straightforward way by walking suffix links for each state (still fine because total states is O(total pattern length) ≤ O(m)).

---

### Step C: Run Dijkstra on an expanded graph (vertex, automaton_state)
We must obey the original graph's connectivity (edges go from `a` to `b`). But penalties depend on recent edge history (automaton state). So we do shortest path on a product graph:

- Node in expanded graph: `(graph_vertex v, automaton_state st)`
- From `(u, st)` for each outgoing original edge `edge_id: u -> v`:
  - `new_st = aho.go(st, edge_id)`
  - transition cost: `c[edge_id] + state_cost[new_st]`
  - relax `(v, new_st)`.

All costs are nonnegative ⇒ Dijkstra works.

Complexity:
- Automaton size = O(m) (because sum pattern lengths ≤ 2m plus m singleton edges).
- Expanded nodes: `(n * states)`, but in practice constrained by `states = O(m)`.
- Each expanded node has ≤ 10 outgoing transitions (outdegree constraint).
So total relaxations are about `O(states * m * 10)` in worst form; works within constraints.

---

### Step D: Recover the actual edge sequence
We store parent pointers:
- `parent[v][st] = (prev_vertex, prev_state)`
- `parent_edge[v][st] = edge_id used`

After Dijkstra, among all states `st`, pick the best `dist[T][st]`, then backtrack to reconstruct the edge list.

---

## 3) C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/strings/aho_corasick.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;
};

const int64_t inf = (int64_t)1e18 + 42;

template<class T = string>
class AhoCorasick {
  private:
    using G = conditional_t<
        is_same_v<T, const char*> || is_same_v<T, char*> || is_array_v<T>, char,
        typename T::value_type>;

    struct State {
        map<G, int> to;
        int link;
        int word_id;
        State() : link(0), word_id(-1) {}
    };

  public:
    vector<State> states;

    AhoCorasick() { clear(); }

    void clear() {
        states.clear();
        states.emplace_back();
    }

    void add_word(const T& word, int id = -1) {
        int u = 0;
        for(const G& c: word) {
            if(!states[u].to.count(c)) {
                states[u].to[c] = states.size();
                states.emplace_back();
            }
            u = states[u].to[c];
        }
        states[u].word_id = id;
    }

    void build() {
        queue<int> Q;
        states[0].link = -1;

        for(auto& [c, v]: states[0].to) {
            states[v].link = 0;
            Q.push(v);
        }

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

            for(auto& [c, v]: states[u].to) {
                int j = states[u].link;
                while(j != -1 && !states[j].to.count(c)) {
                    j = states[j].link;
                }
                states[v].link = (j == -1) ? 0 : states[j].to[c];
                Q.push(v);
            }
        }
    }

    int go(int u, const G& c) const {
        while(u != -1 && !states[u].to.count(c)) {
            u = states[u].link;
        }
        return (u == -1) ? 0 : states[u].to.at(c);
    }

    int link(int u) const { return states[u].link; }
    int word_id(int u) const { return states[u].word_id; }
    int size() const { return states.size(); }

    vector<int> traverse(const T& text) const {
        vector<int> result;
        result.reserve(text.size());
        int u = 0;
        for(const G& c: text) {
            u = go(u, c);
            result.push_back(u);
        }
        return result;
    }

    vector<vector<int>> build_link_tree() const {
        vector<vector<int>> adj(states.size());
        for(int i = 1; i < (int)states.size(); i++) {
            adj[states[i].link].push_back(i);
        }
        return adj;
    }
};

int n, m, r, S, T;
vector<tuple<int, int, int64_t>> edges;
vector<vector<pair<int, int>>> adj;
vector<vector<int>> routes;

void read() {
    cin >> n >> m >> r >> S >> T;
    edges.resize(m);
    adj.resize(n + 1);
    for(int i = 0; i < m; i++) {
        int a, b;
        int64_t c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
        adj[a].push_back({b, i});
    }
    routes.resize(r);
    for(int i = 0; i < r; i++) {
        int k;
        cin >> k;
        routes[i].resize(k);
        for(int j = 0; j < k; j++) {
            cin >> routes[i][j];
            routes[i][j]--;
        }
    }
}

void solve() {
    // We can think of this as a string problem with the alphabet being the
    // edges. In particular, after we decide on the path (string), we want to
    // add an additional cost based on the occurrences of the patterns. Note
    // that the cost contribution from each pattern is known in advance, so we
    // can simply solve the problem that minimizes sum(edges on path) +
    // sum(#pattern occurrences * (sum edges in pattern)).
    //
    // When it comes to patterns, one of the most popular approaches we should
    // think about is Aho–Corasick. Particularly, we can build a trie over the
    // patterns, and precompute the contribution of all patterns that end at a
    // certain state (so that we can later use this). For convenience, for every
    // edge ei, we will add a singleton edge {ei} as a pattern with contribution
    // equal to 0. This is to ensure that during the full path from S to T we
    // will have a non-empty pattern. The number of states is still O(M).
    //
    // Now that we have this trie, we essentially know what node we are in
    // purely based on the current prefix - particularly it's the second
    // endpoint of the last edge (letter). We can think of this as an
    // alternative graph, where the state is the current longest prefix. The
    // transitions are defined based on the last node, and there are at most D =
    // 10 of them (due to the degree constraint). To be more precise, when we
    // add a new edge to the path we are building, we might end up in a state
    // that doesn't exist in the trie and so we will jump back through the fail
    // links until we get something that exists. We will then add the relevant
    // contribution from the patterns + the actual edge cost we added, and this
    // will be the final edge cost in this alternative graph. Afterwards, this
    // is simply a Dijkstra - we have O(M) nodes and O(MD) edges, so this is
    // fast enough.

    AhoCorasick<vector<int>> aho;

    vector<int64_t> pattern_cost(r);
    for(int i = 0; i < r; i++) {
        for(int e: routes[i]) {
            pattern_cost[i] += get<2>(edges[e]);
        }
        aho.add_word(routes[i], i);
    }
    for(int i = 0; i < m; i++) {
        aho.add_word({i});
    }
    aho.build();

    int num_states = aho.size();
    vector<int64_t> end_cost(num_states, 0);
    for(int i = 0; i < r; i++) {
        int st = 0;
        for(int e: routes[i]) {
            st = aho.go(st, e);
        }
        end_cost[st] += pattern_cost[i];
    }

    vector<int64_t> state_cost(num_states, 0);
    for(int u = 0; u < num_states; u++) {
        int cur = u;
        while(cur != -1) {
            state_cost[u] += end_cost[cur];
            cur = aho.link(cur);
        }
    }

    vector<vector<int64_t>> dist(n + 1, vector<int64_t>(num_states, inf));
    vector<vector<pair<int, int>>> parent(
        n + 1, vector<pair<int, int>>(num_states, {-1, -1})
    );
    vector<vector<int>> parent_edge(n + 1, vector<int>(num_states, -1));

    priority_queue<
        tuple<int64_t, int, int>, vector<tuple<int64_t, int, int>>, greater<>>
        pq;

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

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

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

        for(auto [v, edge_id]: adj[u]) {
            int64_t edge_cost = get<2>(edges[edge_id]);
            int new_st = aho.go(st, edge_id);
            int64_t new_dist = d + edge_cost + state_cost[new_st];

            if(new_dist < dist[v][new_st]) {
                dist[v][new_st] = new_dist;
                parent[v][new_st] = {u, st};
                parent_edge[v][new_st] = edge_id;
                pq.push({new_dist, v, new_st});
            }
        }
    }

    int64_t best_dist = inf;
    int best_st = -1;
    for(int st = 0; st < num_states; st++) {
        if(dist[T][st] < best_dist) {
            best_dist = dist[T][st];
            best_st = st;
        }
    }

    if(best_dist == inf) {
        cout << -1 << "\n";
        return;
    }

    vector<int> path;
    int cur_node = T, cur_st = best_st;
    while(parent_edge[cur_node][cur_st] != -1) {
        path.push_back(parent_edge[cur_node][cur_st]);
        auto [prev_node, prev_st] = parent[cur_node][cur_st];
        cur_node = prev_node;
        cur_st = prev_st;
    }
    reverse(path.begin(), path.end());

    cout << best_dist << "\n";
    cout << path.size() << "\n";
    for(int i = 0; i < (int)path.size(); i++) {
        if(i > 0) {
            cout << " ";
        }
        cout << path[i] + 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 (same approach) with detailed comments

```python
import sys
import heapq
from collections import deque

INF = 10**30

# We build an Aho–Corasick automaton where "characters" are edge IDs (ints).
class AhoCorasick:
    def __init__(self):
        # next[state] is a dict: symbol -> next_state
        self.nxt = []
        self.link = []
        self._new_state()          # state 0 = root
        self.link[0] = -1          # root suffix link

    def _new_state(self):
        self.nxt.append({})
        self.link.append(0)
        return len(self.nxt) - 1

    def add_word(self, word):
        """Insert a sequence of integers into the trie."""
        u = 0
        for c in word:
            if c not in self.nxt[u]:
                self.nxt[u][c] = self._new_state()
            u = self.nxt[u][c]
        return u  # return terminal state (useful)

    def build(self):
        """Build suffix links using BFS."""
        q = deque()

        # Initialize children of root: suffix link = root
        for c, v in self.nxt[0].items():
            self.link[v] = 0
            q.append(v)

        # BFS
        while q:
            u = q.popleft()
            for c, v in self.nxt[u].items():
                j = self.link[u]
                while j != -1 and c not in self.nxt[j]:
                    j = self.link[j]
                self.link[v] = 0 if j == -1 else self.nxt[j][c]
                q.append(v)

    def go(self, u, c):
        """Automaton transition with failure links."""
        while u != -1 and c not in self.nxt[u]:
            u = self.link[u]
        return 0 if u == -1 else self.nxt[u][c]

    def size(self):
        return len(self.nxt)


def solve():
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    n = int(next(it))
    m = int(next(it))
    r = int(next(it))
    S = int(next(it))
    T = int(next(it))

    edges = [None] * m           # (a,b,c)
    adj = [[] for _ in range(n + 1)]  # adj[a] = (b, edge_id)

    for i in range(m):
        a = int(next(it)); b = int(next(it)); c = int(next(it))
        edges[i] = (a, b, c)
        adj[a].append((b, i))

    routes = []
    for _ in range(r):
        k = int(next(it))
        route = [int(next(it)) - 1 for __ in range(k)]  # 0-based edge IDs
        routes.append(route)

    # --- Build Aho–Corasick ---
    aho = AhoCorasick()

    # pattern_cost[i] = sum of base edge costs along special route i
    pattern_cost = [0] * r

    # We'll need terminal states to assign end_cost easily.
    terminal_states = [0] * r

    for i, route in enumerate(routes):
        cost = 0
        for e in route:
            cost += edges[e][2]
        pattern_cost[i] = cost
        terminal_states[i] = aho.add_word(route)

    # Add singleton patterns {edge_id} with cost 0 (as in C++ solution)
    for e in range(m):
        aho.add_word([e])

    aho.build()
    num_states = aho.size()

    # end_cost[state] = sum of costs of patterns ending exactly at this state
    end_cost = [0] * num_states
    for i in range(r):
        end_cost[terminal_states[i]] += pattern_cost[i]

    # state_cost[state] = sum of end_cost along suffix chain
    state_cost = [0] * num_states
    for u in range(num_states):
        cur = u
        s = 0
        while cur != -1:
            s += end_cost[cur]
            cur = aho.link[cur]
        state_cost[u] = s

    # --- Dijkstra on expanded states (graph_vertex, automaton_state) ---
    dist = [[INF] * num_states for _ in range(n + 1)]
    parent_node = [[-1] * num_states for _ in range(n + 1)]
    parent_state = [[-1] * num_states for _ in range(n + 1)]
    parent_edge = [[-1] * num_states for _ in range(n + 1)]

    pq = []
    dist[S][0] = 0
    heapq.heappush(pq, (0, S, 0))

    while pq:
        d, u, st = heapq.heappop(pq)
        if d != dist[u][st]:
            continue

        for v, edge_id in adj[u]:
            edge_cost = edges[edge_id][2]
            new_st = aho.go(st, edge_id)
            new_dist = d + edge_cost + state_cost[new_st]

            if new_dist < dist[v][new_st]:
                dist[v][new_st] = new_dist
                parent_node[v][new_st] = u
                parent_state[v][new_st] = st
                parent_edge[v][new_st] = edge_id
                heapq.heappush(pq, (new_dist, v, new_st))

    # Pick best automaton state at destination T
    best_dist = INF
    best_st = -1
    for st in range(num_states):
        if dist[T][st] < best_dist:
            best_dist = dist[T][st]
            best_st = st

    if best_dist >= INF:
        sys.stdout.write("-1\n")
        return

    # Reconstruct edge path
    path = []
    cur_node, cur_st = T, best_st
    while parent_edge[cur_node][cur_st] != -1:
        e = parent_edge[cur_node][cur_st]
        path.append(e)
        pn = parent_node[cur_node][cur_st]
        ps = parent_state[cur_node][cur_st]
        cur_node, cur_st = pn, ps
    path.reverse()

    # Output (edge IDs must be 1-based)
    sys.stdout.write(str(best_dist) + "\n")
    sys.stdout.write(str(len(path)) + "\n")
    if path:
        sys.stdout.write(" ".join(str(e + 1) for e in path) + " \n")
    else:
        sys.stdout.write("\n")


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

---

## 5) Compressed editorial

Model the traveled path as a sequence of edge IDs. Each special route is a pattern; whenever it occurs as a contiguous subpath, add an extra penalty equal to the route's total edge cost. Build an Aho–Corasick automaton over all special routes (plus singleton edges with cost 0). Precompute for each automaton state `st` the total penalty of all patterns that end at this position: `state_cost[st]` = sum of `end_cost` over `st` and its suffix-link ancestors.

Run Dijkstra on expanded nodes `(vertex, st)`. For each graph edge `edge_id: u→v`, transition `st→new_st = go(st, edge_id)` with cost `c[edge_id] + state_cost[new_st]`. The best answer is `min_st dist[T][st]`. Store parents to reconstruct the optimal edge sequence.
