#include<bits/stdc++.h>
#define int long long
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;
const int N = 1e5+5;
const int INF = 1e17;
struct Infor{
int u, c, w;
};
vector<Infor> E[2*N];
map<int,vector<pair<int,int>>> E_color[2*N];
int dp[N];
map<int,int> dp2[N];
map<int,int> color[N], sum[N];
int n, m;
/*
đi từ u -> v bằng cạnh màu c , trọng số w
(Ta sẽ đổi màu các cạnh còn lại kết nối với u có màu c)
dp[v] = dp[u] + sum[u][c] - w
đi từ u --> v bằng cách đổi màu c của canh với trọng số w
dp[v] = dp[u] + w
đi từ u --> v bằng cách dổi màu c của cạnh với trọng số w, tuy nhiên khi ta đi tiếp từ v sang cạnh có màu c.
Thì do đổi màu c của cạnh hiện tại rồi nên nó không làm ảnh hưởng đến cạnh phía sau và ta có thể đi qua cạnh này mà
không tốn chi phí, vậy ta sẽ khoang tạm tính trọng số của việc đổi cạnh này mà để sang v tính
dp2[v][c] = dp[u]
Từ đỉnh v chưa tính trọng số của việc đổi màu cạnh trước đó ta buocj phải đi qua cạnh có màu
*/
struct Node {
int d, u, type;
bool operator<(const Node &other) const{
return d >other.d;
}
};
void Dijkstra() {
fill(dp, dp+n+1, INF);
priority_queue<Node> pq;
pq.push({0, 1, 0});
dp[1] = 0;
while(!pq.empty()) {
Node res = pq.top(); pq.pop();
int u = res.u;
int d = res.d;
int type = res.type;
if(type == 0) {
if(d > dp[u]) continue;
for(Infor &tmp: E[u]) {
int w = tmp.w;
int v = tmp.u;
int c = tmp.c;
if(dp[v] > dp[u] + sum[u][c] - w) {
dp[v] = dp[u] + sum[u][c] - w;
pq.push({dp[v], v, 0});
}
if(dp[v] > dp[u] + w) {
dp[v] = dp[u] + w;
pq.push({dp[v], v, 0});
}
if(!dp2[v].count(c) || dp2[v][c] > dp[u]) {
dp2[v][c] = dp[u];
pq.push({dp[v], v, c});
}
}
}
else {
if(d < dp2[u][type]) continue;
for(pair<int,int> &tmp: E_color[u][type]) {
int v = tmp.first;
int w = tmp.second;
if(dp[v] > dp2[u][type] + sum[u][type] - w) {
dp[v] = dp2[u][type] + sum[u][type] - w;
pq.push({dp[v], v, 0});
}
}
}
}
}
void solve() {
cin >> n >> m;
for(int i=1; i<=m; i++) {
int u, v, c, p; cin >> u >> v >> c >> p;
E[u].push_back({v, c, p});
E[v].push_back({u, c, p});
E_color[u][c].push_back({v, p});
E_color[v][c].push_back({u, p});
color[u][c]++;
color[v][c]++;
sum[u][c] += p;
sum[v][c] += p;
}
Dijkstra();
cout << (dp[n] == INF ? -1: dp[n]) <<'\n';
}
signed main() {
if(fopen("input.txt", "r")) freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);cin.tie(0);
int T = 1;
// cin >> T;
while(T--) solve();
}
