#include<vector>
#include <string>
#include<algorithm>
#include <iostream>
#include <queue>
#include<set>
#include<cmath>
#include<math.h>
using namespace std;
#define ll long long
#define pll pair<long long, long long>
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define cin(a) for(ll ghgh = 0; ghgh<a.size(); ghgh++) cin>>a[ghgh];
#define pcin(a) for(ll ghgh = 0; ghgh<a.size(); ghgh++) cin>>a[ghgh].first>>a[ghgh].second;
#define cout(a) for(ll ghgha = 0; ghgha<a.size(); ghgha++) cout<<a[ghgha]<<" ";
#define pcout(a) for(ll ghgha = 0; ghgha<a.size(); ghgha++) cout<<a[ghgha].first<<" "<<a[ghgha].second<<endl;
const ll inf = 1e9 + 7, llinf = 1e18 + 123;
void xru() {
    setlocale(LC_ALL, "rus");
    /*freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


struct tp {
    ll a, b, c;
};





int main()
{
    xru();
    while (true) {
        ll vn = (ll)rand()  + 2, vm = (ll)rand() % (vn*(vn-1)/2);
        vector<tp>vs(vm);
        for (ll i = 0; i < vm; i++) {
            vs[i].a = 1 + (ll)rand() % (vn);
            vs[i].b = 1 + (ll)rand() % (vn);
            vs[i].c = (ll)rand() % vn;
        }
        ll n, m;
        //cin » n » m;
        n = vn, m = vm;
        cout << n << " " << m << endl;
        vector<tp>id(m);
        vector < vector < pll>>g(n), check(n, vector<pll>(n, { 0, 0 }));
        for (ll i = 0; i < m; i++) {
            ll x, y, cnt;
            // cin » x » y » cnt;
            x = vs[i].a;
            y = vs[i].b;
            cnt = vs[i].c;
            cout << x << " " << y << " "<<  cnt << endl;
            x--, y--;
            id[i].a = x, id[i].b = y, id[i].c = cnt;
            if (x == y) continue;
            if (check[x][y].first == 0) {
                check[x][y] = { 1, cnt };
                check[y][x] = check[x][y];
            }
            else {
                check[x][y].second = min(check[x][y].second, cnt);
                check[y][x] = check[x][y];
            }
        }
        for (ll i = 0; i < m; i++) {
            if (id[i].a == id[i].b) {
                continue;
            }
            if (check[id[i].a][id[i].b].first == 1) {
                g[id[i].a].push_back({ id[i].b, check[id[i].a][id[i].b].second });
                g[id[i].b].push_back({ id[i].a, check[id[i].a][id[i].b].second });
                check[id[i].a][id[i].b].first = 0;
                check[id[i].b][id[i].a].first = 0;
            }
        }
        queue<ll>q;
        vector<pll>prev(n, { -1, -1 });
        vector<ll>dist(n, inf);
        vector<bool>used(n, false);
        dist[n - 1] = 0;
        used[n - 1] = true;
        q.push(n - 1);
        while (!q.empty()) {
            ll x = q.front();
            q.pop();
            for (ll i = 0; i < g[x].size(); i++) {
                pll to = g[x][i];
                if (dist[x] + 1 < dist[to.first]) {
                    prev[to.first] = { x, to.second };
                    dist[to.first] = dist[x] + 1;
                }
                else if (dist[x] + 1 == dist[to.first]) {
                    if (to.second < prev[to.first].second) {
                        prev[to.first] = { x, to.second };
                    }
                }
                if (!used[to.first]) {
                    used[to.first] = true;
                    q.push(to.first);
                }
            }
        }
        vector<ll>ans;
        ll x = 0;
        ll i = 0;
        while (prev[x].first != -1) {
            // cout « x « " " « prev[x].first « " " « prev[x].second « endl;
            ans.push_back(prev[x].second);
            x = prev[x].first;
            i++;
        }

        cout << ans.size() << endl;
        cout(ans);
        cout << endl << endl;


    }
}