#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 1e5 + 5;
const int N = 1e9 + 7;
const ll INF = 1e18;
struct edge{
int to, p, c;
edge(){}
edge(int _to, int _p, int _c) : to(_to), p(_p), c(_c){}
};
vector<edge> adj[maxn];
map<int, int> col[maxn];
map<int, ll> dist[maxn], ttl[maxn]; // dist[pos][0] = no change
int main(void){
fastio;
int n, m;
cin>>n>>m;
for(int i = 0; i < m; i++){
int a, b, c, p;
cin>>a>>b>>c>>p;
a--, b--;
adj[a].pb(edge(b, p, c));
adj[b].pb(edge(a, p, c));
col[a][c] ++, col[b][c] ++;
ttl[a][c] += p, ttl[b][c] += p;
}
for(int i = 0; i < n; i++){
for(auto [c, cnt] : col[i]) dist[i][c] = INF;
dist[i][0] = INF;
}
dist[0][0] = 0;
priority_queue<pll, vector<pll>, greater<pll>> q;
q.push({0, 0});
while(!q.empty()){
auto [d, pos] = q.top(); q.pop();
if(dist[pos][0] != d) continue;
for(auto [x, p, c] : adj[pos]){
dist[x][c] = min(dist[x][c], dist[pos][0]);
if(dist[x][0] > dist[pos][0] + p) dist[x][0] = dist[pos][0] + p, q.push({dist[x][0], x});
if(dist[x][0] > min(dist[pos][c], dist[pos][0]) + ttl[pos][c] - p) dist[x][0] = min(dist[pos][c], dist[pos][0]) + ttl[pos][c] - p, q.push({dist[x][0], x});
}
}
cout<<(dist[n - 1][0] < INF ? dist[n - 1][0] : -1)<<"\n";
}
