import std.stdio, std.string, std.conv;
import std.algorithm, std.array;
import std.container, std.typecons;
 
auto solve(string s_) {
    auto NM = s_.split.map!(to!int)();
    immutable N=NM[0], M=NM[1];
    alias Tuple!(int,"p",int,"c") G;
    auto g = new G[][N];
    foreach(_;0..M) {
        auto pqc = readln.split.map!(to!int)();
        immutable p=pqc[0]-1, q=pqc[1]-1, c=pqc[2];
        g[p]~=G(q,c);
        g[q]~=G(p,c);
    }
    alias Tuple!(int,"d",G,"t") T;
    BinaryHeap!(Array!T,"a>b") q;
    q.insert(T(0,G(0,-1)));
    bool[G] u;
    while(!q.empty()) {
        immutable v = q.front;
        q.popFront();
        if(v.t.p == N-1) return v.d;
        if(v.t in u) continue;
        u[v.t]=true;
        foreach(ref w;g[v.t.p]) {
            if(w in u) continue;
            q.insert(T(v.d+(v.t.c==w.c?0:1),w));
        }
    }
    return -1;
}
void main(){ for(string s; (s=readln.chomp()).length;) writeln(solve(s)); }