1. Abridged Problem Statement  
Given a directed graph with N vertices and M edges, each edge colored 1, 2, or 3, find the minimum number of edges in a walk from vertex 1 to vertex N such that no two consecutive edges have the same color. If no such path exists, print –1.

2. Detailed Editorial  

Problem restatement  
- Vertices are numbered from 1 to N.  
- Edges are directed and each carries one of three possible colors (1, 2, 3).  
- You must travel from vertex 1 to vertex N, minimizing the total number of edges used, under the constraint that you cannot take two edges of the same color in a row.

Key observations  
- Every time you traverse an edge, its color matters relative to the previous edge’s color.  
- A standard shortest-path algorithm on vertices only is not enough, because the “state” must also remember the color of the edge just taken.  

State definition  
Define state (u, c) = “you are at vertex u, and the last edge used to reach u had color c.” We index colors from 0 to 2 internally instead of 1–3.

Transitions  
From state (u, last_color), you may follow any outgoing edge e = (u → v) of color col ≠ last_color, moving to state (v, col) with an added cost of 1.

Initialization  
- We start at vertex 1 with no previous edge, so we can model this by allowing initial “last_color” to be any of 0,1,2, all at distance 0.  
- Then perform a breadth-first search (BFS) over the augmented state space of size N×3 = up to 600.  

Distance array  
dist[u][c] = minimum number of edges to reach vertex u with last edge color = c.

Answer  
Once BFS completes, look at dist[N][0], dist[N][1], dist[N][2], and take the minimum. If still infinite, answer is –1.

Time & memory  
- States: O(3N) = O(N).  
- Transitions: each edge is considered at most 3 times (once for each possible last_color ≠ edge_color). So O(3M).  
- N ≤ 200, M ≤ N² = 40 000 is easily handled in 0.25 s.

3. 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;
};

const int inf = (int)1e9;

int n, m;
vector<vector<pair<int, int>>> adj;

void read() {
    cin >> n >> m;
    adj.assign(n, {});
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--, w--;
        adj[u].push_back({v, w});
    }
}

void solve() {
    // Shortest path where consecutive edges must differ in colour, found by BFS
    // over the state (vertex, colour of the last edge used). dist[v][c] is the
    // fewest edges to reach v with the last edge coloured c. We seed all three
    // colours at the source with distance 0 so the very first edge may have any
    // colour; from state (u, w) we relax every outgoing edge (u -> v) of colour
    // w2 != w. Since all edges have weight 1, plain BFS gives the optimum, and
    // the answer is the minimum dist[n-1][c] over the three colours, or -1 if
    // the target is unreachable.

    vector<vector<int>> dist(n, vector<int>(3, inf));
    dist[0] = {0, 0, 0};

    queue<pair<int, int>> q;
    q.push({0, 0});
    q.push({0, 1});
    q.push({0, 2});

    while(!q.empty()) {
        auto [u, w] = q.front();
        q.pop();
        for(auto [v, w2]: adj[u]) {
            if(w != w2 && dist[v][w2] > dist[u][w] + 1) {
                dist[v][w2] = dist[u][w] + 1;
                q.push({v, w2});
            }
        }
    }

    int ans = min({dist[n - 1][0], dist[n - 1][1], dist[n - 1][2]});
    if(ans == inf) {
        cout << -1 << '\n';
    } else {
        cout << ans << '\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 with Detailed Comments  

```python
from collections import deque
import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    
    # Build adjacency list: adj[u] = list of (v, color)
    # We'll store colors as 0,1,2 internally
    adj = [[] for _ in range(n)]
    for _ in range(m):
        u = int(next(it)) - 1
        v = int(next(it)) - 1
        c = int(next(it)) - 1
        adj[u].append((v, c))
    
    INF = 10**9
    # dist[u][c] = shortest #edges to reach u with last edge color c
    dist = [[INF]*3 for _ in range(n)]
    # Starting at vertex 0 with any 'last color'
    for c in range(3):
        dist[0][c] = 0
    
    # BFS queue of (vertex, last_color)
    q = deque()
    for c in range(3):
        q.append((0, c))
    
    while q:
        u, last_color = q.popleft()
        d = dist[u][last_color]
        # Traverse all outgoing edges
        for v, c in adj[u]:
            if c != last_color and dist[v][c] > d + 1:
                dist[v][c] = d + 1
                q.append((v, c))
    
    # Answer is the minimum over last_color at vertex n-1
    ans = min(dist[n-1])
    print(-1 if ans >= INF else ans)

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

5. Compressed Editorial  

- Model each state as (vertex, last_edge_color) to enforce the “no two adjacent edges share the same color” constraint.  
- Initialize all three “last_color” variants at the source with distance 0 and run a BFS on this expanded state space.  
- Each transition uses exactly one more edge (cost=1) and is allowed only if the new edge’s color differs from last_color.  
- Final answer = min distance for (N, any color), or –1 if unreachable.