#ifdef LOCAL
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define sz(v) ((int)(v).size())
#define me(f, x) memset(f, x, sizeof(f))
#define mc(f, g) memcpy(f, g, sizeof(f))
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE ".in", "r", stdin), freopen(FILE ".out", "w", stdout)
using namespace std;

using vi = vector<int>;
#endif

constexpr int N = 1e5 + 9;
int n, m;

int dfn[N], low[N], dfc;
int eu[N], ev[N], ew[N];
vector<pair<int, int>> g[N];

int stk[N], tp;

int cnt;
vi bcc[N];
int id[N];

void dfs(int u, int f) {
  stk[++tp] = u;
  dfn[u] = low[u] = ++dfc;
  for (auto p : g[u]) {
    int v = p.first;
    if (v == f) {
      continue;
    }
    if (!dfn[v]) {
      dfs(v, u);
      low[u] = min(low[u], low[v]);
    } else {
      low[u] = min(low[u], dfn[v]);
    }
  }
  if (dfn[u] == low[u]) {
    ++cnt;
    while (1) {
      int v = stk[tp--];
      id[v] = cnt;
      bcc[cnt].eb(v);
      if (v == u) {
        break;
      }
    }
  }
}

int S, T, hd[N], tot = 1;

struct edg {
  int v, nx, w, i;
} e[N * 2];

IL void add_edge(int u, int v, int i) {
  e[++tot] = {v, hd[u], 1, i};
  hd[u] = tot;
  e[++tot] = {u, hd[v], 1, i};
  hd[v] = tot;
}

int dep[N], pre[N];

void bfs() {
  me(dep, 0);
  dep[S] = 1;
  queue<int> q;
  q.push(S);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = hd[u], v; i; i = e[i].nx) {
      v = e[i].v;
      if (e[i].w && !dep[v]) {
        dep[v] = dep[u] + 1;
        pre[v] = i;
        q.push(v);
      }
    }
  }
  assert(dep[T]);
}

void BFS () {
  me(dep, 0);
  dep[S] = 1;
  queue<int> q;
  q.push(S);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = hd[u], v; i; i = e[i].nx) {
      v = e[i].v;
      if (!e[i].w && !dep[v]) {
        dep[v] = dep[u] + 1;
        pre[v] = i;
        q.push(v);
      }
    }
  }
  assert(dep[T]);
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  L(i, 1, m) {
    int u, v;
    cin >> u >> v >> ew[i];
    eu[i] = u;
    ev[i] = v;
    g[u].eb(v, i);
    g[v].eb(u, i);
  }
  dfs(1, 0);
  int ns = 0, p = -1;
  L(i, 1, cnt) {
    int mx = -1e9, mn = 1e9;
    for (int u : bcc[i]) {
      for (auto [v, x] : g[u]) {
        if (id[v] == i) {
          mx = max(mx, ew[x]);
          mn = min(mn, ew[x]);
        }
      }
    }
    if (mx - mn > ns) {
      ns = mx - mn;
      p = i;
    }
  }
  cout << ns << '\n';
  int X = 0, Y = 0;
  vector<tuple<int, int, int>> E;
  for (int u : bcc[p]) {
    for (auto [v, x] : g[u]) {
      if (id[v] == p) {
        E.eb(u, v, x);
        if (!X || ew[x] > ew[X]) {
          X = x;
        }
        if (!Y || ew[x] < ew[Y]) {
          Y = x;
        }
      }
    }
  }
  S = n + 1;
  T = n + 2;
  add_edge(S, eu[X], -1);
  add_edge(S, ev[X], -1);
  add_edge(eu[Y], T, -1);
  add_edge(ev[Y], T, -1);
  for (auto [u, v, x] : E) {
    if (x == X || x == Y) {
      continue;
    }
    if (u < v) {
      add_edge(u, v, x);
    }
  }
  L(_, 0, 1) {
    bfs();
    int x = T;
    while (x != S) {
      int i = pre[x];
      e[i].w -= 1;
      e[i ^ 1].w += 1;
      x = e[i ^ 1].v;
    }
  }
  vi ans[2];
  L (_, 0, 1) {
    BFS();
    int x = T;
    while (x != S) {
      int i = pre[x];
      e[i].w += 1;
      e[i ^ 1].w -= 1;
      ans[_].eb(x);
      x = e[i ^ 1].v;
    }
    ans[_].erase(ans[_].begin());
  }
  reverse(ans[1].begin(), ans[1].end());
  cout << sz(ans[0]) + sz(ans[1]) << '\n';
  for (int x : ans[0]) {
    cout << x << ' ';
  }
  for (int y : ans[1]) {
    cout << y << ' ';
  }
  cout << '\n';
}
// I love WHQ!