#include <cstdio>
#include <cstring>

const int MAXN = 35;
const int MAXM = 1010;

struct EDGE {
  int v, w, next;
} edge[MAXM];

int head[MAXN], edgeNum;
void AddEdge(int u, int v, int w) {
  edge[++edgeNum] = {v, w, head[u]};
  head[u] = edgeNum;
}

int k;
int del[MAXM], deleted[MAXM];
int ans[MAXM], cost = 0x7fffffff;
int que[MAXN], front, tail;
bool vis[MAXN];
int end;
void check() {
  // printf("[");
  // for (int i = 1; i <= k; ++i) {
  // printf("%d%c", del[i], " ]"[i == k]);
  // }
  // printf("\n");
  memset(deleted, 0, sizeof deleted);
  for (int i = 1; i <= k; ++i) {
    deleted[del[i]] = 1;
  }
  memset(vis, 0, sizeof vis);
  front = tail = 0;
  que[++tail] = 1;
  bool canreach = false;
  while (front != tail) {
    int u = que[++front];
    if (u == end) {
      canreach = true;
      break;
    }
    vis[u] = 1;
    // printf("{\n");
    // printf("\tu = %d\n", u);
    for (int i = head[u]; i; i = edge[i].next) {
      int v = edge[i].v;
      if (vis[v] || deleted[i]) continue;
      // printf("\tedgeid = %d, v = %d\n", i, v);
      que[++tail] = v;
    }
    // printf("\n}\n");
  }
  if (!canreach) {
    int ncost = 0;
    for (int i = 1; i <= k; ++i) {
      ncost += edge[del[i]].w;
    }
    if (ncost < cost) {
      cost = ncost;
      for (int i = 1; i <= k; ++i) {
        ans[i] = del[i];
      }
    }
  }
}
void dfs(int now) {
  if (now == k + 1) {
    return check();
  }
  for (int i = del[now - 1] + 1; i <= edgeNum; ++i) {
    del[now] = i;
    dfs(now + 1);
  }
}

int n, m;

int main() {
  freopen("milk6.in", "r", stdin);
  freopen("milk6.out", "w", stdout);
  scanf("%d %d", &n, &m);
  end = n;
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    AddEdge(u, v, w);
  }

  for (k = 1; k <= m; ++k) {
    // printf("[k = %d]\n", k);
    del[0] = 0;
    dfs(1);
    if (cost != 0x7fffffff) {
      printf("%d %d\n", cost, k);
      for (int i = 1; i <= k; ++i) {
        printf("%d\n", ans[i]);
      }
      return 0;
    }
  }
  return 0;
}