#include <bits/stdc++.h>
#define fo(i,m,n) for(int i=m;i<=n;i++)
#define fod(i,n,m) for(int i=n;i>=m;i--)
#define fo1(i,m,n,k) for(int i=m;i<=n;i=i+k)
#define fod1(i,n,m,k) for(int i=n;i>=m;i=i-k)
#define fol(i,m,n) for(long long i=m;i<=n;i++)
#define fodl(i,n,m) for(long long i=n;i>=m;i--)
#define fo1l(i,m,n,k) for(long long i=m;i<=n;i=i+k)
#define fod1l(i,n,m,k) for(long long i=n;i>=m;i=i-k)
#define lb lower_bound
#define ub upper_bound
#define pii pair <int,int>
#define vii vector<pii>
#define ll long long
#define fi first
#define se second
#define si size()
#define pb push_back
#define ppb pop_back()
#define fr front()
#define et empty()
#define bg begin()
#define ub upper_bound
#define lb lower_bound
#define ed end()
#define el endl
#define EL cout << '\n';
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
const int M = 1e3 + 5;
int n, m;
map <pii, int> dem;
struct zata{
int u, v, c, val;
}d[10 * N];
bool kts2 = true;
void inp(){
cin >> n >> m;
fo(i, 1, m){
cin >> d[i].u >> d[i].v >> d[i].c >> d[i].val;
if(d[i].val != 1) kts2 = false;
dem[{d[i].u, d[i].c}] += 1;
dem[{d[i].v, d[i].c}] += 1;
}
}
ll s[10 * N];
bool dd[10 * N];
vii adj[10 * N];
ll dfs1(int u, ll sum){
if(u == n) return sum;
ll mn = 1e18 + 19;
for(pii it : adj[u]){
int v = it.fi, val = it.se;
if(dd[v]) continue;
dd[v] = true;
mn = min(mn, dfs1(v, sum + val));
dd[v] = false;
}
return mn;
}
void dijsktra(int x){
fo(i, 1, n){
s[i] = 1e18;
dd[i] = false;
}
s[x] = 0;
priority_queue <pii, vector<pii>, greater <pii>> q;
q.push({0, x});
while(q.si){
pii it = q.top();
q.pop();
int u = it.se;
if(dd[u] == 1) continue;
dd[u] = 1;
for(pii wt : adj[u]){
int v = wt.fi, val = wt.se;
if(s[v] > s[u] + val){
s[v] = s[u] + val;
q.push({s[v], v});
}
}
}
}
void sub1(){
if(m < n - 1){
cout << -1;
return;
}
fo(i, 1, m){
if(dem[{d[i].u, d[i].c}] == 1) adj[d[i].u].pb({d[i].v, 0});
else adj[d[i].u].pb({d[i].v, d[i].val});
if(dem[{d[i].v, d[i].c}] == 1) adj[d[i].v].pb({d[i].u, 0});
else adj[d[i].v].pb({d[i].u, d[i].val});
}
fo(i, 1, n) dd[i] = false;
dd[1] = true;
ll ans = dfs1(1, 0);
cout << ans;
}
void sub2(){
if(m < n - 1){
cout << -1;
return;
}
fo(i, 1, m){
if(dem[{d[i].u, d[i].c}] == 1) adj[d[i].u].pb({d[i].v, 0});
else adj[d[i].u].pb({d[i].v, d[i].val});
if(dem[{d[i].v, d[i].c}] == 1) adj[d[i].v].pb({d[i].u, 0});
else adj[d[i].v].pb({d[i].u, d[i].val});
}
dijsktra(1);
cout << s[n];
}
void solve(){
sub2();
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
inp();
solve();
return 0;
}
