#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define clr(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define mp make_pair
#define INF 0x3f3f3f3f
typedef vector<int> VI;
typedef pair<int, int> PII;
const int maxn = 5e5 + 5;
// head

struct Edge
{
    int v;
    int cost;
    Edge(int _v = 0, int _cost = 0): v(_v), cost(_cost) {}
};
struct qnode
{
    int v, c;
    qnode(int _v = 0, int _c = 0): v(_v), c(_c) {}
};
vector<Edge>E[maxn];
void addedge(int u, int v, int w)
{
    E[u].push_back(Edge(v, w));
}

map<PII, int> mll;
int num;
int getid(int u, int c)
{
    if(mll[mp(u,c)] == 0)
        mll[mp(u,c)] = ++num;
    return mll[mp(u,c)];
}

qnode dq[maxn*2];
int vis[maxn];
int bfs(int n)
{
    memset(vis, 0, sizeof(vis));
    int l = num, r = num;
    dq[--l] = qnode(1, 0);
    vis[1] = 1;
    while(l < r)
    {
        qnode s = dq[l++];
        if(s.v == n) return s.c;
        rep(i, 0, E[s.v].size())
        {
            int v = E[s.v][i].v;
            int cost = E[s.v][i].cost;
            if(vis[v]) continue;
            if(cost == 0)
                dq[--l] = qnode(v, s.c);
            else
                dq[r++] = qnode(v, s.c+1);
            vis[v] = 1;
        }
    }
    return -2;
}

struct FastIO
{
    static const int S = 1310720;
    int wpos;
    char wbuf[S], endofFile;
    FastIO() : wpos(0), endofFile(0) {}
    inline int xchar()
    {
        if(endofFile) exit(0);
        static char buf[S];
        static int len = 0, pos = 0;
        if(pos == len)
            pos = 0, len = fread(buf, 1, S, stdin);
        if(pos == len)
        {
            endofFile = 1;
            return '\n';
        }
        return buf[pos ++];
    }
    inline unsigned long long xuint()
    {
        int c = xchar();
        unsigned long long x = 0;
        while(c <= 32)
            c = xchar();
        for(; '0' <= c && c <= '9'; c = xchar())
            x = x * 10 + c - '0';
        return x;
    }
    inline long long xint()
    {
        long long s = 1;
        int c = xchar(), x = 0;
        while(c <= 32)
            c = xchar();
        if(c == '-')
            s = -1, c = xchar();
        for(; '0' <= c && c <= '9'; c = xchar())
            x = x * 10 + c - '0';
        return x * s;
    }
    inline void xstring(char *s)
    {
        int c = xchar();
        while(c <= 32)
            c = xchar();
        for(; c > 32; c = xchar())
            * s++ = c;
        *s = 0;
    }
    inline double xdouble()
    {
        bool sign = 0;
        char ch = xchar();
        double x = 0;
        while(ch <= 32)
            ch = xchar();
        if(ch == '-')
            sign = 1, ch = xchar();
        for(; '0' <= ch && ch <= '9'; ch = xchar())
            x = x * 10 + ch - '0';
        if(ch == '.')
        {
            double tmp = 1;
            ch = xchar();
            for(; ch >= '0' && ch <= '9'; ch = xchar())
                tmp /= 10.0, x += tmp * (ch - '0');
        }
        if(sign)
            x = -x;
        return x;
    }
    inline void wchar(int x)
    {
        if(wpos == S)
            fwrite(wbuf, 1, S, stdout), wpos = 0;
        wbuf[wpos ++] = x;
    }
    inline void wint(long long x)
    {
        if(x < 0)
            wchar('-'), x = -x;
        char s[24];
        int n = 0;
        while(x || !n)
            s[n ++] = '0' + x % 10, x /= 10;
        while(n--)
            wchar(s[n]);
    }
    inline void wstring(const char *s)
    {
        while(*s)
            wchar(*s++);
    }
    inline void wdouble(double x, int y = 6)
    {
        static long long mul[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000LL, 100000000000LL, 1000000000000LL, 10000000000000LL, 100000000000000LL, 1000000000000000LL, 10000000000000000LL, 100000000000000000LL};
        if(x < -1e-12)
            wchar('-'), x = -x;
        x *= mul[y];
        long long x1 = (long long) floorl(x);
        if(x - floor(x) >= 0.5)
            ++x1;
        long long x2 = x1 / mul[y], x3 = x1 - x2 * mul[y];
        wint(x2);
        if(y > 0)
        {
            wchar('.');
            for(size_t i = 1; i < y && x3 * mul[i] < mul[y]; wchar('0'), ++i);
            wint(x3);
        }
    }
    ~FastIO()
    {
        if(wpos)
            fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
} io;


int main()
{
#ifndef ONLINE_JUDGE
    // freopen("in.txt", "r", stdin);
#endif

    int n, m;
    // while(scanf("%d%d", &n, &m) != EOF)
    while(n = io.xint())
    {
        m = io.xint();
        mll.clear();
        num = n;
        while(m--)
        {
            int u, v, c;
            u = io.xint();
            v = io.xint();
            c = io.xint();
            // scanf("%d%d%d", &u, &v, &c);
            int uc = getid(u, c);
            int vc = getid(v, c);
            addedge(u, uc, 1);
            addedge(uc, u, 1);
            addedge(uc, vc, 0);
            addedge(vc, uc, 0);
            addedge(vc, v, 1);
            addedge(v, vc, 1);
        }
        printf("%d\n", bfs(n)/2);
        rep(i, 1, num+1) E[i].clear();
    }
    return 0;
}

Measured memory_bytes: 66048