//Mikolaj Tofiluk
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int MAXN=100007;
ll INF=1e18;
map<int,ll> odl[MAXN];//0 - bez zmiany, 1 - przyszedl z zmienionej oryginalnie 1, 2 - przyszedl z zmienionej oryginalnie 2
vector<pair<int,pair<int,ll>>> graf[MAXN];//kolor u cena-zmiany
map<int,ll> suma_cen[MAXN];
map<int,bool> odw[MAXN];
int n,m;
void fastscan_ll(ll &number) {
bool negative = false;
register char c;
number = 0;
c = getchar();
if (c=='-'){
negative = true;
c = getchar();
}
for (; (c>47 && c<58); c=getchar())
number = number *10 + c - 48;
if (negative)
number *= -1;
}
void fastscan_int(int &number) {
bool negative = false;
register char c;
number = 0;
c = getchar();
if (c=='-'){
negative = true;
c = getchar();
}
for (; (c>47 && c<58); c=getchar())
number = number *10 + c - 48;
if (negative)
number *= -1;
}
void wczytanie(){
fastscan_int(n);fastscan_int(m);
int a,b,k;
ll c;
for (int i=0;i<m;i++){
fastscan_int(a);fastscan_int(b);fastscan_int(k);fastscan_ll(c);
graf[a].push_back({k,{b,c}});
graf[b].push_back({k,{a,c}});
suma_cen[a][k]+=c;
suma_cen[b][k]+=c;
}
}
void djikstra(){
for (int i=1;i<=n;i++){
odl[i][0]=INF;
for (pair<int,pair<int,ll>> u:graf[i]) odl[i][u.first]=INF;
}
priority_queue<pair<pair<ll,int>,int>> q; //cena v kolor_tej_co_zmienilem
q.push({{0,1},0});
odl[1][0]=0;
int v,kolor,u,x;
ll c,xc;
while (q.size()>0){
v=q.top().first.second;
x=q.top().second;
q.pop();
if (odw[v][x]) continue;
odw[v][x]=1;
for (pair<int,pair<int,ll>> syf:graf[v]){
kolor=syf.first;u=syf.second.first;c=syf.second.second;
if (x==0 && odl[v][x]+min(suma_cen[v][kolor]-c,c)<odl[u][0]){
odl[u][0]=min(suma_cen[v][kolor]-c,c)+odl[v][x];
q.push({{-odl[u][0],u},0});
}
if (x==0 && odl[u][kolor]>odl[v][x]){
odl[u][kolor]=odl[v][x];
q.push({{-odl[u][kolor],u},kolor});
}
if (x!=0 && kolor==x && odl[u][0]>odl[v][x]+suma_cen[v][x]-c){
odl[u][0]=odl[v][x]+suma_cen[v][x]-c;
q.push({{-odl[u][0],u},0});
}
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
wczytanie();
djikstra();
ll w=odl[n][0];
if (w==INF) cout<<-1;
else cout<<w;
}
