#[allow(unused_imports)]
use std::cmp::{min,max};
#[allow(unused_imports)]
use std::collections::BTreeMap;
#[allow(unused_imports)]
use std::ops::*;
#[allow(unused_imports)]
use std::collections::BinaryHeap;

fn main() {
    let (n,m) = {
        let xs = read_vec_i64();
        (xs[0] as usize, xs[1] as usize)
    };
    let (edges,companies) = {
        // (v,c) -> vec![next_v]
        let mut edges = BTreeMap::new();
        for i in 0..n {
            edges.insert((i,0), vec![i]);
        }
        let mut companies = vec![vec![]; n];
        for _ in 0..m {
            let xs = read_vec_i64();
            let (p,q,c) = ((xs[0]-1) as usize, (xs[1]-1) as usize, xs[2]);
            edges.entry((p,c)).or_insert(vec![q]).push(q);
            edges.entry((q,c)).or_insert(vec![p]).push(p);
            companies[p].push(c);
            companies[q].push(c);
        }
        (edges,companies)
    };
    // (v, c) -> d
    let mut dists = BTreeMap::new();
    //dists.insert((0,0),0);
    // (-d, v, c)
    let mut heap = BinaryHeap::new();
    heap.push((0,0,0));
    while ! heap.is_empty() {
        let (neg_d, v, c) = heap.pop().unwrap();
        let d = -neg_d;
        if let Some(&prev_d) = dists.get(&(v,c)) {
            if prev_d < d {
                continue;
            }
        }
        if c == 0 {
            for &company in &companies[v] {
                let next_d = d+1;
                match dists.get(&(v,company)) {
                    Some(&prev_d) => {
                        if prev_d <= next_d {
                            continue;
                        }
                    }
                    None => {
                    }
                }
                //println!("{},{} -> {}", v, e_c, next_d);
                dists.insert((v,company),next_d);
                heap.push((-next_d, v, company));
            }
        }
        else {
            for &c2 in &[0,c] {
                if let Some(es) = edges.get(&(v,c2)) {
                    for &next in es {
                        let next_d = d;
                        if let Some(&prev_d) = dists.get(&(next,c2)) {
                            if prev_d <= next_d {
                                continue;
                            }
                        }
                        //println!("{},{} -> {}", next, e_c, next_d);
                        dists.insert((next,c2), next_d);
                        heap.push((-next_d, next, c2));
                    }
                }
            }
        }
    }
    match dists.get(&(n-1,0)) {
        Some(&d) => {
            println!("{}", d);
        }
        None => {
            println!("-1");
        }
    }
}

#[allow(dead_code)]
fn read_line() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok();
    ret.pop();
    return ret;
}

#[allow(dead_code)]
fn read_i64() -> i64 {
    let ss = read_line();
    return ss.parse::<i64>().unwrap();
}

#[allow(dead_code)]
fn read_vec_i64() -> Vec<i64> {
    let mut res = vec![];
    let ss = read_line();
    for ts in ss.split_whitespace() {
        let x = ts.parse::<i64>().unwrap();
        res.push(x);
    }
    return res;
}

use std::fmt::Display;
#[allow(dead_code)]
fn write_vec<T: Display>(xs: &Vec<T>) {
    if xs.len() == 0 {
        println!("");
        return;
    }
    print!("{}", xs[0]);
    for i in 1..xs.len() {
        print!(" {}", xs[i]);
    }
    println!("");
}


Measured memory_bytes: 80124