#include <bits/stdc++.h>
#define int long long
#define data _data
using namespace std;
struct edge {
int to, c, p;
};
struct data {
int v, c, type, e;
};
bool operator<(edge a, edge b) {
if (a.to != b.to)
return a.to < b.to;
if (a.c != b.c)
return a.c < b.c;
return a.p < b.p;
}
const int N = 1e5 + 5, M = 2e5 + 5, inf = 1e18;
unordered_map<int, vector<pair<edge, int>>> g[N];
unordered_map<int, int> dp[N], psum[N];
unordered_map<int, data> pre[N];
//int C[M];
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
set<int> av;
for(int i = 1; i <= m; i++)
av.insert(i);
for (int i = 1; i <= m; i++) {
int u, v, c, p;
cin >> u >> v >> c >> p;
g[u][c].push_back({{v, c, p}, i});
g[v][c].push_back({{u, c, p}, i});
psum[u][c] += p;
psum[v][c] += p;
// C[i] = c;
// av.erase(c);
}
dp[1][0] = 0;
priority_queue<edge> pq;
pq.push({0, 1, 0});
while (pq.size()) {
auto [cost, v, c] = pq.top();
cost = -cost;
pq.pop();
if (c) {
if (dp[v][c] != cost) continue;
for (auto [i, num]: g[v][c]) {
int case0 = psum[v][c] - i.p + cost;
if (!dp[i.to].count(0) || case0 < dp[i.to][0]) {
dp[i.to][0] = case0;
pre[i.to][0] = {v, c, 0, num};
pq.push({-dp[i.to][0], i.to, 0});
}
}
} else {
if (dp[v][0] != cost) continue;
for (auto &i: g[v]) {
for (auto [j, num]: i.second) {
int case1 = psum[v][j.c] - j.p + cost;
if (!dp[j.to].count(0) || case1 < dp[j.to][0]) {
dp[j.to][0] = case1;
pre[j.to][0] = {v, c, 1, num};
pq.push({-dp[j.to][0], j.to, 0});
}
int case2 = j.p + cost;
if (!dp[j.to].count(0) || case2 < dp[j.to][0]) {
dp[j.to][0] = case2;
pre[j.to][0] = {v, c, 2, num};
pq.push({-dp[j.to][0], j.to, 0});
}
int case3 = cost;
if (!dp[j.to].count(j.c) || case3 < dp[j.to][j.c]) {
dp[j.to][j.c] = case3;
pre[j.to][j.c] = {v, c, 3, num};
pq.push({-dp[j.to][j.c], j.to, j.c});
}
}
}
}
}
if (dp[n].count(0))
cout << dp[n][0];
else {
cout << -1;
return 0;
}
cout << "\n";
int v = n, c = 0;
vector<int> way = {n};
vector<int> e;
while (make_pair(v, c) != make_pair(1LL, 0LL)) {
auto [nv, nc, type, num] = pre[v][c];
if (type <= 1) {
for (auto [i, j]: g[nv][C[num]])
if (j != num)
e.push_back(j);
} else if(type == 2) {
e.push_back(num);
}
v = nv;
c = nc;
way.push_back(v);
}
reverse(way.begin(), way.end());
// cout << way.size() << '\n';
for(int i : way)2 * 2;
// cout << i << " ";
// cout << '\n' << e.size() << '\n';
for(int i : e) {
// cout << i << " " << *av.begin() << '\n';
av.erase(av.begin());
}
return 0;
}
