Infinite March: Maximizing Weight under Alternating Graph Constraints

You are given two undirected connected weighted graphs \(G_1(V_1, E_1)\) and \(G_2(V_2, E_2)\), each having \(n\) vertices. A group of scouts starts at vertex \(s\) and must eventually reach vertex \(t\). However, they traverse the graphs in an alternating fashion.

More precisely, suppose the scouts are currently at vertex \(x\). Then:

• On the 1^st, 3^rd, 5^th, … move they choose an edge \((x,y,w)\) in \(E_1\) (i.e. from graph \(G_1\)), with weight \(w\). This move is only allowed if \[ \operatorname{dist}_1(x,t) > \operatorname{dist}_1(y,t), \] where \(\operatorname{dist}_1(x,t)\) denotes the shortest-path distance between \(x\) and \(t\) in \(G_1\).
• On the 2^nd, 4^th, 6^th, … move, they choose an edge \((x,y,w)\) in \(E_2\) (i.e. from graph \(G_2\)), with weight \(w\). This move is only allowed if \[ \operatorname{dist}_2(x,t) > \operatorname{dist}_2(y,t), \] where \(\operatorname{dist}_2(x,t)\) denotes the shortest-path distance between \(x\) and \(t\) in \(G_2\).

Your task is to find the maximum possible sum of edge weights from \(s\) to \(t\), following the move restrictions above. Note that if the scouts can delay reaching \(t\) indefinitely (by cycling in a way that each cycle obeys the conditions and adds a positive total weight), then the answer is infinite.

Input/Output details: See the input and output descriptions below.

inputFormat

The first line contains five integers \(n\), \(m_1\), \(m_2\), \(s\), \(t\) \((1 \leq s,t \leq n)\). Here, \(n\) is the number of vertices, \(m_1\) is the number of edges in \(G_1\) and \(m_2\) is the number of edges in \(G_2\).

The following \(m_1\) lines each contain three integers \(u\), \(v\), \(w\) describing an undirected edge in \(G_1\) between vertices \(u\) and \(v\) with weight \(w\).

The next \(m_2\) lines each contain three integers \(u\), \(v\), \(w\) describing an undirected edge in \(G_2\) between vertices \(u\) and \(v\) with weight \(w\).

outputFormat

If the maximum route weight is finite, output a single integer representing it. Otherwise, if the scouts can avoid reaching \(t\) indefinitely while accumulating arbitrarily large weight, output the string Infinite.

sample

3 3 3 1 3
1 2 5
2 3 5
1 3 1
1 2 2
2 3 2
1 3 10

1