int solve()
{
    int n, m;
    scanf("%d %d", &n, &m);
    vector<vector<pii>> g(n);
    for (int i = 0; i < m; ++i)
    {
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        --x, --y;
        g[x].inb(mk(y, c));
        g[y].inb(mk(x, c));
    }
    vector<vi> d(n, vi(9, 0));
    vi dst(n, INF);
    set<pair<pair<int, vi>, int>> q;
    dst[0] = 0;
    q.insert(mk(mk(0, d[0]), 0));
    while (!q.empty())
    {
        vi cur = q.begin()->X.Y;
        int u = q.begin()->Y;
        q.erase(*q.begin());
        for (auto tt : g[u])
        {
            int to = tt.X;
            int c = tt.Y;
            if (c == 0)
            {
                if (dst[to] > dst[u] || dst[to] == dst[u] && d[to] > d[u])
                {
                    q.erase(mk(mk(dst[to], d[to]), to));
                    d[to] = cur;
                    dst[to] = dst[u];
                    q.insert(mk(mk(dst[to], d[to]), to));
                }
            }
            else
            {
                cur[c - 1]++;
                if (dst[to] > dst[u] + 1 || dst[to] == dst[u] + 1 && d[to] > cur)
                {
                    q.erase(mk(mk(dst[to], d[to]), to));
                    d[to] = cur;
                    dst[to] = dst[u] + 1;
                    q.insert(mk(mk(dst[to], d[to]), to));
                }
                cur[c - 1]--;
            }
        }
    }
    vi ans = d[n - 1];
    if (dst[n - 1] == 0)
        puts("0"), exit(0);
    for (int i = 0; i < 9; ++i)
    {
        for (int j = 0; j < ans[i]; ++j)
            printf("%d", i + 1);
    }
    puts("");
    return 0;
}