#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin() , (x).end()
const ll MOD = 998244353;
const long double EPS = 0.000000001;
const double PI = 3.14159265358979323846;
const int nx[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
const int ny[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
ll n, m, color[100005], cost[1005][2005]; bool vis[100005];
vector<pair<int, pair<int, int>>>adj[100005];
bool dfs(int v) {
if(v==n) return true;
vis[v]=true;
for(auto u:adj[v]) {
if(vis[u.ss.ff]) continue;
if(dfs(u.ss.ff)) return true;
}
return false;
}
int32_t main()
{
ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int l=0;l<m;l++) {
ll a, b, c, p; cin>>a>>b>>c>>p; color[l]=c;
adj[a].pb({l, {b, p}}); adj[b].pb({l, {a, p}});
cost[a][c]+=p; cost[b][c]+=p;
}
if(!dfs(1)) { cout<<-1; return 0; }
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
pq.push({0, 1}); vector<ll>d(n+1, MOD); d[1]=0;
while(!pq.empty()) {
ll a=pq.top().ss, w=pq.top().ff; pq.pop();
if(d[a]<w) continue;
for(auto u:adj[a]) {
ll curr=INT_MAX;
for(int l=1;l<=m;l++) {
if(l==color[u.ff]) curr=min(curr, cost[a][l]-u.ss.ss);
else curr=min(curr, cost[a][l]+u.ss.ss);
}
if(d[a]+curr<d[u.ss.ff]) {
d[u.ss.ff]=d[a]+curr;
pq.push({d[u.ss.ff], u.ss.ff});
}
}
}
cout<<d[n]<<'\n';
return 0;
}
