import std.algorithm;
import std.array;
import std.ascii;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;
int size(T)(in T s) { return cast(int)s.length; }

struct Edge {
    int from, to, company;
}

void main() {
    int N, M; readf("%s %s\n", &N, &M);
    auto Graph = new Edge[][N];
    foreach (i; 0 .. M) {
        int p, q, c; readf("%s %s %s\n", &p, &q, &c);
        p--; q--; c--;
        Graph[p] ~= Edge(p, q, c);
        Graph[q] ~= Edge(q, p, c);
    }
    struct T { int node; int company; }
    auto G = new T[][N];
    foreach (node; Graph) {
        foreach (edge; node) {
            int from = edge.from;
            int to = edge.to;
            int company = edge.company;
            G[from] ~= T(to, company);
        }
    }

    struct State { T node_stat; int cost; }
    BinaryHeap!(Array!State, "a.cost > b.cost") PQ;
    foreach (edge; Graph[0]) { // edges from node-0
        PQ.insert (
            State(T(0, edge.company), 1)
        );
    }
    int[T] dist;
    while (! PQ.empty) {
        State cur = PQ.front; PQ.removeFront;
        T stat = cur.node_stat;
        auto cost = cur.cost;
        foreach (next_edge; G[stat.node]) {
            int ncost;
            if (next_edge.company == stat.company) {
                // then transit is not needed. we don't have to pay another charge.
                ncost = cost;
            } else {
                ncost = cost + 1;
            }
            if (next_edge !in dist || dist[next_edge] > ncost) {
                dist[next_edge] = ncost;
                PQ.insert(State(next_edge, ncost));
            }
        }
    }
    int ans = int.max;
    foreach (k, v; dist) {
        //writeln("[", k, ",", v, "]");
        auto node = k.node;
        if (node == N - 1) {
            ans = min(ans, v);
        }
    }
    if (ans == int.max) {
        writeln(-1);
    } else {
        writeln(ans);
    }
}
