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

103. Traffic Lights
Time limit per test: 0.25 second(s)
Memory limit: 4096 kilobytes
input: standard
output: standard



In the city of Dingilville the traffic is arranged in an unusual way. There are junctions and roads connecting the junctions. There is at most one road between any two different junctions. There is no road connecting a junction to itself. Travel time for a road is the same for both directions. At every junction there is a single traffic light that is either blue or purple at any moment. The color of each light alternates periodically: blue for certain duration and then purple for another duration. Traffic is permitted to travel down the road between any two junctions, if and only if the lights at both junctions are the same color at the moment of departing from one junction for the other. If a vehicle arrives at a junction just at the moment the lights switch it must consider the new colors of lights. Vehicles are allowed to wait at the junctions. You are given the city map which shows:
the travel times for all roads (integers)
the durations of the two colors at each junction (integers)
and the initial color of the light and the remaining time (integer) for this color to change at each junction.

Your task is to find a path which takes the minimum time from a given source junction to a given destination junction for a vehicle when the traffic starts. In case more than one such path exists you are required to report only one of them.

Input
The first line contains two numbers: The id-number of the source junction and the id-number of the destination junction. The second line contains two numbers: N, M. The following N lines contain information on N junctions. The (i+2)'th line of the input file holds information about the junction i : Ci, riC, tiB, tiP where Ci is either B for blue or P for purple, indicating the initial color of the light at the junction i. Finally, the next M lines contain information on M roads. Each line is of the form: i, j, lij where i and j are the id-numbers of the junctions which are connected by this road. 2 ≤ N ≤ 300 where N is the number of junctions. The junctions are identified by integers 1 through N. These numbers are called id-numbers. 1 ≤ M ≤ 14000 where M is the number of roads. 1 ≤ lij ≤ 100 where lij is the time required to move from junction i to j using the road that connects i and j. 1 ≤ tiC ≤ 100 where tiC is the duration of the color c for the light at the junction i. The index c is either 'B' for blue or 'P' for purple. 1 ≤ riC ≤ tiC where riC is the remaining time for the initial color c at junction i.

Output
If a path exists:
The first line will contain the time taken by a minimum-time path from the source junction to the destination junction.
Second line will contain the list of junctions that construct the minimum-time path you have found. You have to write the junctions to the output file in the order of travelling. Therefore the first integer in this line must be the id-number of the source junction and the last one the id-number of the destination junction.

If a path does not exist:
A single line containing only the integer 0.

Example(s)
sample input
sample output
1 4
4 5
B 2 16 99
P 6 32 13
P 2 87 4
P 38 96 49
1 2 4
1 3 40
2 3 75
2 4 76
3 4 77
127
1 2 4

<|response|>
1. Abridged Problem Statement
You are given an undirected graph with N junctions (nodes) and M roads (edges). Each junction i has a traffic light that alternates between blue (duration tB_i) and purple (duration tP_i), starting in color C_i with r_i time units remaining in that initial color. You can wait at junctions for free. You may traverse an edge (u, v) of travel time w only at a departure time T when both lights at u and v display the same color. Your goal is to get from a given source S to a destination D in the minimum possible time, and output that time plus one valid path. If no feasible path exists, print 0.

2. Key Observations
- The availability of an edge (u, v) depends on your departure time T, because you need both lights to match at that instant.
- Each light has a simple periodic schedule with an “initial segment” of length r_i (the remaining time in C_i), then it alternates indefinitely in blocks of lengths tB_i and tP_i.
- We can write a function get_color(i, T) that returns the color (blue/purple) at junction i at global time T, and another function time_to_next_color(i, T) giving the wait until the next color switch.
- To traverse (u, v) from time T, we may have to wait at u until the earliest T' ≥ T such that get_color(u, T') == get_color(v, T'). That T' can be found by “stepping forward” to the next switch of u or v (whichever is sooner), and repeating until colors match (in practice only a few steps).
- Once we can compute the earliest departure T' for each neighbor v from u at current time T, we have a time-dependent edge weight T' + w(u,v). We can plug this into a standard Dijkstra’s algorithm by treating the cost to reach v as that arrival time.
- We record a parent[v] pointer whenever we improve dist[v] so that we can reconstruct the path at the end.

3. Full Solution Approach
a. Data Structures
   - Store for each junction i a tuple (isBlueInit, remInit, tB, tP).
   - Adjacency list: for each u, vector of (v, w_uv).
   - Arrays dist[i] = best known arrival time at i, initialized to ∞ except dist[S] = 0.
   - parent[i] = predecessor of i on the best path.

b. Functions on Light Phases
   1. get_color(i, T):
      - If T < remInit[i], return the initial color.
      - Else reduce by the initial segment and (if the initial color was blue) by the following purple block, then index into the repeating cycle of length tB[i] + tP[i].
   2. time_to_next_color(i, T):
      - If T < remInit[i], return remInit[i] - T.
      - Else compute the position inside the current block and return the remaining time until that block ends.

c. Synchronizing Two Junctions
   first_time_same_color(u, v, T):
      - Repeat up to a small constant number of times (e.g. 3):
         • If get_color(u, T) == get_color(v, T), return T.
         • Otherwise compute du = time_to_next_color(u, T), dv = time_to_next_color(v, T), and advance T by min(du, dv).
      - If still no match, return −1 (treat as “never synchronizes soon”).

d. Time-Dependent Dijkstra
   - Use a min-heap keyed by current known arrival time.
   - Pop (t, u).
   - For each neighbor (v, w):
     • let depart = first_time_same_color(u, v, t). If depart < 0, skip.
     • let arrive = depart + w. If arrive < dist[v], update dist[v]=arrive, parent[v]=u, push (arrive, v).
   - Continue until heap is empty.

e. Output
   - If dist[D] is still ∞, print 0.
   - Otherwise print dist[D] on the first line. Reconstruct the path by following parent[] from D back to S, reverse it, and print the sequence of junction IDs (1-based).

4. C++ Implementation
```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;
};

int n, m, source, destination;
vector<tuple<bool, int, int, int>> junctions;
vector<vector<pair<int, int>>> adj;

void read() {
    cin >> source >> destination;
    source--, destination--;
    cin >> n >> m;

    junctions.resize(n);
    for(int i = 0; i < n; ++i) {
        char ci;
        int ri, tb, tp;
        cin >> ci >> ri >> tb >> tp;
        junctions[i] = make_tuple(ci == 'B', ri, tb, tp);
    }

    adj.assign(n, {});
    for(int i = 0; i < m; ++i) {
        int from, to, length;
        cin >> from >> to >> length;
        from--, to--;
        adj[from].push_back({to, length});
        adj[to].push_back({from, length});
    }
}

void solve() {
    // Dijkstra on (junction, time), where a road can only be traversed while
    // both endpoints show the same colour.
    //
    // Each junction is described by (initial colour, remaining time r of that
    // colour, blue duration tB, purple duration tP). get_color returns the
    // colour at absolute time t and time_to_next_color the wait until it next
    // flips; first_time_same_color advances t (waiting at the current
    // junction) until both endpoints agree, returning the earliest such moment
    // or -1 if they never align within a few flips.
    //
    // The Dijkstra state is the arrival time at a junction. To relax an edge we
    // wait for a matching colour, then add the road length. parent[] lets us
    // reconstruct one minimum-time path; if the destination is unreachable we
    // print 0.

    function<int(int, int)> get_color = [&](int u, int t) -> int {
        auto [is_blue, r, tb, tp] = junctions[u];
        if(t < r) {
            return is_blue;
        }

        if(is_blue && t < r + tp) {
            return 0;
        } else if(is_blue) {
            r += tp;
        }

        int cycle = tb + tp;
        int tu = (t - r) % cycle;
        return (int)(tu < tb);
    };

    function<int(int, int)> time_to_next_color = [&](int u, int t) {
        auto [is_blue, r, tb, tp] = junctions[u];
        if(t < r) {
            return r - t;
        }

        int cycle = tb + tp;
        if(is_blue && t < r + tp) {
            return r + tp - t;
        } else if(is_blue) {
            r += tp;
        }

        int tu = (t - r) % cycle;
        return tu < tb ? (tb - tu) : (cycle - tu);
    };

    function<int(int, int, int)> first_time_same_color =
        [&](int u, int v, int t) {
            for(int attempt = 0; attempt < 3; attempt++) {
                if(get_color(v, t) == get_color(u, t)) {
                    return t;
                }

                int dtu = time_to_next_color(u, t);
                int dtv = time_to_next_color(v, t);
                t += min(dtu, dtv);
            }

            return -1;
        };

    vector<int> dist(n, INT_MAX);
    vector<int> parent(n, -1);
    priority_queue<
        pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>
        pq;

    pq.push({0, source});
    dist[source] = 0;
    while(!pq.empty()) {
        auto [t, u] = pq.top();
        pq.pop();

        for(auto [v, w]: adj[u]) {
            int first_time = first_time_same_color(u, v, t);
            if(first_time == -1) {
                continue;
            }

            int new_time = first_time + w;
            if(new_time < dist[v]) {
                parent[v] = u;
                dist[v] = new_time;
                pq.push({new_time, v});
            }
        }
    }

    if(dist[destination] == INT_MAX) {
        cout << "0\n";
        return;
    }

    vector<int> path;
    int u = destination;
    while(u != -1) {
        path.push_back(u + 1);
        u = parent[u];
    }

    reverse(path.begin(), path.end());
    cout << dist[destination] << '\n';
    cout << path << '\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
```python
import sys
import heapq

def read_input():
    data = sys.stdin.read().split()
    it = iter(data)
    S = int(next(it)) - 1
    D = int(next(it)) - 1
    N = int(next(it))
    M = int(next(it))
    # Junction array: each entry is (isBlueInit, remInit, tB, tP)
    J = []
    for _ in range(N):
        C = next(it)
        r = int(next(it))
        b = int(next(it))
        p = int(next(it))
        J.append((C=='B', r, b, p))
    adj = [[] for _ in range(N)]
    for _ in range(M):
        u = int(next(it)) - 1
        v = int(next(it)) - 1
        w = int(next(it))
        adj[u].append((v,w))
        adj[v].append((u,w))
    return S, D, N, J, adj

def get_color(u, T, J):
    isBlue, r, tB, tP = J[u]
    # still in initial block?
    if T < r:
        return isBlue
    T -= r
    cycle = tB + tP
    x = T % cycle
    if isBlue:
        # next block is purple
        if x < tP:
            return False
        x -= tP
        return x < tB
    else:
        # next block is blue
        if x < tB:
            return True
        x -= tB
        return x >= tP  # loops back

def time_to_next_change(u, T, J):
    isBlue, r, tB, tP = J[u]
    if T < r:
        return r - T
    T -= r
    cycle = tB + tP
    x = T % cycle
    if isBlue:
        if x < tP:
            return tP - x
        x -= tP
        return tB - x
    else:
        if x < tB:
            return tB - x
        x -= tB
        return tP - x

def first_sync(u, v, T, J):
    # Try a few phase-change steps
    for _ in range(3):
        if get_color(u, T, J) == get_color(v, T, J):
            return T
        du = time_to_next_change(u, T, J)
        dv = time_to_next_change(v, T, J)
        T += min(du, dv)
    return -1

def solve():
    S, D, N, J, adj = read_input()
    INF = 10**18
    dist = [INF]*N
    parent = [-1]*N
    dist[S] = 0
    pq = [(0, S)]

    while pq:
        t, u = heapq.heappop(pq)
        if t > dist[u]:
            continue
        for v, w in adj[u]:
            depart = first_sync(u, v, t, J)
            if depart < 0:
                continue
            arrive = depart + w
            if arrive < dist[v]:
                dist[v] = arrive
                parent[v] = u
                heapq.heappush(pq, (arrive, v))

    if dist[D] == INF:
        print(0)
        return

    # Reconstruct path
    path = []
    cur = D
    while cur != -1:
        path.append(cur+1)
        cur = parent[cur]
    path.reverse()

    print(dist[D])
    print(*path)

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

Explanation Highlights:
- We treat light-color constraints as a time-dependent edge availability.
- Computing the next feasible departure time between two junctions takes only a few O(1) steps.
- A modified Dijkstra with those dynamic edge-cost computations still runs in O((N+M) log N), efficient for N≤300, M≤14 000.
