DULICH

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 101;
const int oo = 1e9 + 7;

typedef pair<ll, int> ii;

int n, m;
vector<int> a[N];
ll cost[N][N];

ll parent[N], d[N];

void dijkstra(int s) {
    priority_queue<ii, vector<ii>, greater<ii>> pq;

    fill(d + 1, d + 1 + n, 1e9);
    d[s] = 0;
    pq.push({0, s});

    while(!pq.empty()) {
        int u = pq.top().second;
        int du = pq.top().first;
        pq.pop();

        if(du != d[u]) continue;

        for(int i = 0; i < a[u].size() ;i++) {
            int v = a[u][i];
            int uv = cost[u][v];

            if(d[v] > d[u] + uv) {
                d[v] = d[u] + uv;
                pq.push({d[v], v});
                parent[v] = u;
            }
        }
    }
}

void Print(int s, int t, int mid) {
    ll dem = 1;
    vector<int> res;

    int u = mid, v = s;
    while(u != v) {
        dem++;
        res.push_back(v);
        v = parent[v];
    }

    res.push_back(mid);

    u = mid, v = t;
    while(u != v) {
        dem++;
        res.push_back(v);
        v = parent[v];
    }

    cout << dem << '\n';
    for(int i = 0; i < res.size(); ++i)
        cout << res[i] << ' ';
}

int main()
{
    //freopen("in.txt", "r", stdin);
    freopen("DULICH.inp", "r", stdin);
    freopen("DULICH.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;

    memset(cost, oo, sizeof(cost));
    for(int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        a[u].push_back(v);
        a[v].push_back(u);

        cost[u][v] = min(cost[u][v], (ll)w);
        cost[v][u] = cost[u][v];
    }

    ll ans = oo;
    ll mid = -1, s = -1, t = -1;
    for(int i = 1; i <= n; i++) {
        fill(parent + 1, parent + n + 1, 0);

        dijkstra(i);
        for(int u = 1; u <= n; u++)
            for(int v = u + 1; v <= n; v++)
                if(parent[v] != u && parent[u] != v) {
                    if(ans >= d[u] + d[v] + cost[u][v]) {
                        ans = d[u] + d[v] + cost[u][v];
                        mid = i, s = u, t = v;
                    }
                }
    }

    if(ans == oo)
        cout << 0 << '\n';
    else {
        cout << 1 << '\n';
        cout << ans << '\n';

        fill(parent + 1, parent + n + 1, 0);
        dijkstra(mid);

        Print(s, t, mid) ;
    }
}