Shortest Even-Weighted Path

You are given an undirected graph with n nodes and m edges. Each edge connects two nodes and has a weight. Your task is to find the shortest path from a source node s to a target node t considering only the edges with an even weight.

Formally, let the graph be denoted as \(G=(V,E)\), where \(V\) is the set of nodes and \(E\) is the set of edges. Each edge \((u,v,w)\) has a weight \(w\). You are required to compute the shortest distance \(d(s,t)\) using only edges that satisfy \(w \equiv 0 \pmod{2}\). If no such path exists, output -1.

Note: The path length is defined as the sum of the weights of the edges in the path.

inputFormat

The input is given via standard input (stdin) and has the following format:

n m s t
u1 v1 w1
u2 v2 w2
... 
um vm wm

Where:

• \(n\) is the number of nodes.
• \(m\) is the number of edges.
• \(s\) is the source node.
• \(t\) is the target node.
• Each of the following \(m\) lines contains three integers \(u, v, w\) representing an undirected edge between nodes \(u\) and \(v\) with weight \(w\).

outputFormat

Output the shortest distance from node s to node t using only even-weighted edges. If no such path exists, print -1.

5 6 1 5
1 2 10
1 3 15
2 3 12
2 4 20
3 4 18
4 5 2

32