#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
using namespace std;
using ll = long long;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<map<int, pair<vector<pair<ll, int>>, ll>>> adj(n + 1);
vector<map<int, ll>> sm(n + 1);
while (m--)
{
int a, b, c;
ll p;
cin >> a >> b >> c >> p;
adj[a][c].first.push_back({ p, b }), adj[b][c].first.push_back({ p, a });
adj[a][c].second += p, adj[b][c].second += p;
}
vector<ll> dp1(n + 1, -1);
vector<map<int, ll>> dp2(n + 1);
priority_queue<pair<pair<ll, int>, pair<bool, int>>> djk;
djk.push({ {0, 1}, {false, 0} });
while (!djk.empty())
{
ll d = -djk.top().first.first;
int node = djk.top().first.second, lstc = djk.top().second.second;
bool dp12 = djk.top().second.first;
djk.pop();
if (!dp12) if (dp1[node] == -1)
{
dp1[node] = d;
for (auto edgset : adj[node]) for (pair<ll, int> nxt : edgset.second.first)
{
djk.push({ {-d, nxt.second}, {true, edgset.first} });
djk.push({ {-d - nxt.first, nxt.second}, {false, edgset.first} });
djk.push({ {-d - (edgset.second.second - nxt.first), nxt.second},{false, edgset.first} });
}
}
if (dp12) if (dp2[node].count(lstc) == 0)
{
dp2[node][lstc] = d;
for (pair<ll, int> nxt : adj[node][lstc].first) djk.push({ {-d - (adj[node][lstc].second - nxt.first), nxt.second}, {false, lstc} });
}
}
cout << dp1[n];
}
