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, "to", int, "company", int, "cost") Edge;
    int N, M, p, q, c;
    Edge[][] adj;

    scanf("%d %d", &N, &M);
    adj = new Edge[][](N);
    foreach (i; 0..M) {
        scanf("%d %d %d", &p, &q, &c);
        adj[p-1] ~= Edge(q-1, c-1, 0);
        adj[q-1] ~= Edge(p-1, c-1, 0);
    }


    auto dist = new int[](N);
    fill(dist, INF);
    dist[0] = 0;

    auto queue = new BinaryHeap!(Array!Edge, "a.cost > b.cost");
    queue.insert(Edge(0, -1, 0));

    auto prev = new int[][](N);

    while(!queue.empty) {
        auto cur = queue.front;
        queue.removeFront;

        if (cur.cost > dist[cur.to]+1) continue;

        foreach (next; adj[cur.to]) {
            int fee;
            if (cur.company == next.company || prev[cur.to].canFind(next.company))
                fee = 0;
            else
                fee = 1;

            if (cur.cost + fee > dist[next.to])
                continue;
            if (cur.cost + fee == dist[next.to]) {
                prev[next.to] ~= next.company;
                continue;
            }
            prev[next.to] = [next.company];
            dist[next.to] = cur.cost + fee;
            queue.insert(Edge(next.to, next.company, dist[next.to]));
        }
    }


    writeln(dist[N-1] == INF ? -1 : dist[N-1]);
}
