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

#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define orange(a...) orange_(#a, a)
#define debug(a...) debug_(#a, a)
template <typename i>
void orange_(const char * s, i l, i r) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; l != r; l++)
        cerr << (f++ ? " " : "") << *l;
    cerr << " ]\e[0m\n";
}
template <typename ...T>
void debug_(const char * s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

namespace {

class BCC {
private:
    int n, ecnt;
    vector<vector<pair<int, int>>> g;
    vector<int> dfn, low;
    vector<bool> bridge;
    void dfs(int u, int f) {
        dfn[u] = low[u] = dfn[f] + 1;
        int ch = 0;
        for (auto [v, t] : g[u]) if (v != f) {
            if (dfn[v]) {
                low[u] = min(low[u], dfn[v]);
            } else {
                ++ch;
                dfs(v, u);
                low[u] = min(low[u], low[v]);
                if (low[v] > dfn[u])
                    bridge[t] = true;
            }
        }
    }
public:
    void init(int n_) {
        g.assign(n = n_, vector<pair<int, int>>());
        low.assign(n, ecnt = 0);
        dfn.assign(n, 0);
    }
    void add_edge(int u, int v) {
        g[u].emplace_back(v, ecnt);
        g[v].emplace_back(u, ecnt++);
    }
    void solve() {
        bridge.assign(ecnt, false);
        for (int i = 0; i < n; ++i)
            if (not dfn[i]) dfs(i, i);
    }
    bool is_bridge(int x) const { return bridge[x]; }
};

using Pii = pair<int, int>;
constexpr int kInf = 1 << 30;
constexpr int maxn = 100000 + 10;

struct E {
    int to, rev, cost, flow;
};
struct MCMF {
    int n{}, m{}, s{}, t{};
    vector<E> graph[maxn];
    int64_t dis[maxn] = {}, h[maxn] = {};
    int p[maxn] = {};
    void Init(int nn) { n = nn; }
    void AddEdge(int u, int v, int f, int c) {
        graph[u].push_back({v, int(graph[v].size()), c, f});
        graph[v].push_back({u, int(graph[u].size()) - 1, -c, 0});
    }
    bool Dijkstra(int &max_flow, int64_t &cost) {
        priority_queue<Pii, vector<Pii>, greater<>> pq;
        fill_n(dis, n, kInf);
        dis[s] = 0;
        pq.emplace(0, s);
        while (not pq.empty()) {
            auto u = pq.top();
            pq.pop();
            int v = u.second;
            if (dis[v] < u.first) continue;
            for (auto &e : graph[v]) {
                auto new_dis = dis[v] + e.cost + h[v] - h[e.to];
                if (e.flow > 0 and dis[e.to] > new_dis) {
                    dis[e.to] = new_dis;
                    p[e.to] = e.rev;
                    pq.emplace(dis[e.to], e.to);
                }
            }
        }
        if (dis[t] == kInf) return false;
        for (int i = 0; i < n; ++i)
            h[i] += dis[i];
        int d = max_flow;
        for (int u = t; u != s; u = graph[u][p[u]].to) {
            auto &e = graph[u][p[u]];
            d = min(d, graph[e.to][e.rev].flow);
        }
        max_flow -= d;
        cost += int64_t(d) * h[t];
        for (int u = t; u != s; u = graph[u][p[u]].to) {
            auto &e = graph[u][p[u]];
            e.flow += d;
            graph[e.to][e.rev].flow -= d;
        }
        return true;
    }
    int MincostMaxflow(int ss, int tt, int max_flow, int64_t &cost) {
        this->s = ss, this->t = tt;
        cost = 0;
        fill_n(h, n, 0);
        auto orig_max_flow = max_flow;
        while (Dijkstra(max_flow, cost) && max_flow);
        return orig_max_flow - max_flow;
    }
    vector<pair<int, int>> gao() {
        vector<pair<int, int>> ret;
        for (int i = 0; i < n; i++) {
            for (auto e : graph[i])
                if (e.flow == 0 and e.cost > 0)
                    ret.emplace_back(i, e.to);
        }
        return ret;
    }
} flow;

bool vis[maxn]; size_t la[maxn];
vector<pair<int, int>> G[maxn];
void Euler( int u, vector< int >& vec ) {
    while ( la[ u ] < G[ u ].size() ) {
        if( vis[ G[ u ][ la[ u ] ].second ] ) {
            ++ la[ u ];
            continue;
        }
        int v = G[ u ][ la[ u ] ].first;
        vis[ G[ u ][ la[ u ] ].second ] = true;
        ++ la[ u ]; Euler( v, vec );
        vec.push_back( v );
    }
}


} // namespace

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m; 
    cin >> n >> m;
    vector<tuple<int, int, int>> e(m);
    for (auto &[u, v, w] : e) {
        cin >> u >> v >> w;
        --u, --v;
    }

    BCC bcc;
    bcc.init(n);
    for (auto [u, v, w] : e) bcc.add_edge(u, v);
    bcc.solve();

    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; ++i) {
        if (bcc.is_bridge(i)) continue;
        auto [u, v, w] = e[i];
        g[u].emplace_back(v, i);
        g[v].emplace_back(u, i);
    }

    vector<pair<int, int>> cur;
    vector<bool> vis(n);
    auto dfs = [&](auto self, int i) -> void {
        vis[i] = true;
        for (auto [j, x] : g[i]) {
            cur.emplace_back(get<2>(e[x]), x);
            if (vis[j]) continue;
            self(self, j);
        }
    };

    tuple<int, int, int> ans = {0, -1, -1};
    for (int i = 0; i < n; ++i) {
        if (vis[i]) continue;
        cur.clear();
        dfs(dfs, i);
        if (cur.size() < 2) continue;
        sort(cur.begin(), cur.end());
        int x = cur[0].second, y = cur.back().second;
        ans = max(ans, {get<2>(e[y]) - get<2>(e[x]), x, y});
    }
    assert(get<1>(ans) != -1);

    cout << get<0>(ans) << '\n';
    flow.Init(n + 4);
    for (int i = 0; i < m; ++i) {
        if (bcc.is_bridge(i)) continue;
        auto [u, v, w] = e[i];
        if (i == get<1>(ans)) {
            flow.AddEdge(n, u, 1, 1);
            flow.AddEdge(n, v, 1, 1);
        } else if (i == get<2>(ans)) {
            flow.AddEdge(u, n + 1, 1, 1);
            flow.AddEdge(v, n + 1, 1, 1);
        } else {
            flow.AddEdge(u, v, 1, 1);
            flow.AddEdge(v, u, 1, 1);
        }
    }
    flow.AddEdge(n + 2, n, 2, 0);
    flow.AddEdge(n + 1, n + 3, 2, 0);
    int64_t tmp;
    assert(flow.MincostMaxflow(n + 2, n + 3, 2, tmp) == 2);

    auto [a, b, w1] = e[get<1>(ans)];
    auto [c, d, w2] = e[get<2>(ans)];

    int cnt = 0;
    auto es = flow.gao();
    for (auto [u, v] : es) {
        if (v >= n or u >= n) continue;
        G[u].emplace_back(v, cnt);
        G[v].emplace_back(u, cnt++);
    }
    G[a].emplace_back(b, cnt);
    G[b].emplace_back(a, cnt++);
    G[c].emplace_back(d, cnt);
    G[d].emplace_back(c, cnt++);

    vector<int> path;
    Euler(a, path);
    cout << path.size() << '\n';
    for (size_t i = 0; i < path.size(); ++i)
        cout << path[i] + 1 << " \n"[i + 1 == path.size()];
    return 0;
}