import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.stdio, std.bitmanip;
 
 
void main() {
    immutable int INF = 2^^30;
    alias Tuple!(int, "st", int, "company") Node;
    
    int N, M, p, q, c;
 
    scanf("%d %d", &N, &M);
    Node[][Node] adj;
    auto cs = new int[][](N);
    foreach (i; 0..M) {
        scanf("%d %d %d", &p, &q, &c);
        adj[Node(p-1, c)] ~= Node(q-1, c);
        adj[Node(q-1, c)] ~= Node(p-1, c);
        if (!cs[p-1].canFind(c)) cs[p-1] ~= c;
        if (!cs[q-1].canFind(c)) cs[q-1] ~= c;
    }

    foreach (i; 0..N) {
        auto L = cs[i].length;
        foreach (j; 0..L) {
            foreach (k; j+1..L) {
                adj[Node(i, cs[i][j])] ~= adj[Node(i, cs[i][k])];
                adj[Node(i, cs[i][k])] ~= adj[Node(i, cs[i][j])];
            }
        }
    }
    
    alias Tuple!(int, "to", int, "company", int, "cost") Route;
    auto queue = new BinaryHeap!(Array!Route, "a.cost > b.cost");

    int[Node] dist;
    foreach (i; 0..N) {
        foreach (j; cs[i]) {
            if (i == 0) {
                queue.insert(Route(i, j, 1));
                dist[Node(i, j)] = 1;
            }
            else {
                dist[Node(i, j)] = INF;
            }
        }
    }
 
    while(!queue.empty) {
        auto cur = queue.front;
        queue.removeFront;
 
        if (cur.cost > dist[Node(cur.to, cur.company)]) continue;
 
        foreach (next; adj[Node(cur.to, cur.company)]) {
            int fee = (cur.company != next.company);
            if (cur.cost + fee >= dist[next]) continue;
            dist[next] = cur.cost + fee;
            queue.insert(Route(next.st, next.company, dist[next]));
        }
    }
 
    int ans = INF;
    foreach (i; cs[N-1]) {
        ans = min(ans, dist[Node(N-1, i)]);
    }
    writeln(ans == INF ? -1 : ans);
}
