#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define pii pair < int, int >
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
const int N = 1e5+10, M = 2e5+10;
int n, m;
map < pii, vector < pair < int, ll > > > adjc;
vector < pair < pii, ll > > adj[N];
map < pii, bool > vis;
ll price[N];
using namespace std;
void task( void ) {
int a, b, c;
ll p;
cin >> n >> m;
for(int i = 0; i < m; i++) {
cin >> a >> b >> c >> p;
a--; b--; c--;
adj[a].pb(mp(mp(b, c), p));
adj[b].pb(mp(mp(a, c), p));
adjc[mp(a, c)].pb(mp(b, p));
adjc[mp(b, c)].pb(mp(a, p));
}
ll tempsum;
vector < pair < int, ll > > :: iterator itrs, itre;
for(int i = 0; i < n; i++) {
for(int j = 0; j < (int) adj[i].size(); j++) {
if(!vis[mp(i, adj[i][j].F.S)]) {
tempsum = 0;
vis[mp(i, adj[i][j].F.S)] = 1;
itrs = adjc[mp(i, adj[i][j].F.S)].begin();
itre = adjc[mp(i, adj[i][j].F.S)].end();
while(itrs != itre) {
tempsum += itrs -> S;
itrs++;
}
itrs = adjc[mp(i, adj[i][j].F.S)].begin();
while(itrs != itre) {
adj[i].pb(mp(mp(itrs -> F, -1), tempsum - (itrs -> S)));
itrs++;
}
}
}
for(int j = 0; j < (int) adj[i].size(); j++) {
vis[mp(i, adj[i][j].F.S)] = 0;
}
}
set < pair < ll, pii > > dijkstra;
dijkstra.insert(mp(0, mp(0, -1)));
pair < ll, pii > temp;
int pos, col, val;
while(!dijkstra.empty()) {
temp = *dijkstra.begin();
dijkstra.erase(dijkstra.begin());
pos = temp.S.F;
col = temp.S.S;
val = temp.F;
// cout << pos << " " << col << " " << val << "\n";
if(!vis[mp(pos, -1)]) {
vis[mp(pos, -1)] = 1;
price[pos] = val;
for(int i = 0; i < (int) adj[pos].size(); i++) {
if(!vis[mp(adj[pos][i].F.F, adj[pos][i].F.S)] && adj[pos][i].F.S != -1) {
vis[mp(adj[pos][i].F.F, adj[pos][i].F.S)] = 1;
tempsum = 0;
itrs = adjc[mp(adj[pos][i].F.F, adj[pos][i].F.S)].begin();
itre = adjc[mp(adj[pos][i].F.F, adj[pos][i].F.S)].end();
while(itrs != itre) {
tempsum += itrs -> S;
itrs++;
}
itrs = adjc[mp(adj[pos][i].F.F, adj[pos][i].F.S)].begin();
while(itrs != itre) {
dijkstra.insert(mp(val + tempsum - (itrs -> S), mp(itrs -> F, -1)));
itrs++;
}
}
dijkstra.insert(mp(val + adj[pos][i].S, mp(adj[pos][i].F.F, adj[pos][i].F.S)));
}
}
}
if(vis[mp(n - 1, -1)]) cout << price[n - 1] << "\n";
else cout << -1 << "\n";
return;
}
int main( void ) {
FIO;
task();
return 0;
}
