#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 7;
vector<array<int,3>> g[N];
map<int,int> dp2[N],sum[N];
int dp[N],n,m;
struct Node
{
int u,c,dist;
bool operator < (const Node &other) const
{
return dist > other.dist;
}
};
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int u,v,c,p;
cin >> u >> v >> c >> p;
g[u].push_back({v,c,p});
g[v].push_back({u,c,p});
sum[u][c] += p;
sum[v][c] += p;
}
fill(dp+1,dp+n+1,1e18);
dp[1] = 0;
priority_queue<Node> q;
q.push({1,0,0});
while(!q.empty())
{
auto [u,c,dist] = q.top(); q.pop();
if(c != 0)
{
if(dp2[u][c] != dist) continue;
for(auto [v,color,p] : g[u]) if(color == c)
{
int value = dist + sum[u][color] - p;
if(dp[v] > value)
{
dp[v] = value;
q.push({v,0,dp[v]});
}
}
}
else
{
if(dp[u] != dist) continue;
for(auto [v,color,p] : g[u])
{
int value = dist + sum[u][color] - p;
if(dp[v] > value)
{
dp[v] = value;
q.push({v,0,dp[v]});
}
value = dist + p;
if(dp[v] > value)
{
dp[v] = value;
q.push({v,0,dp[v]});
}
if(!dp2[v].count(color) || dp2[v][color] > dist)
{
dp2[v][color] = dist;
q.push({v,color,dp2[v][color]});
}
}
}
}
cout << dp[n];
}
