#include <bits/stdc++.h>
using namespace std;
enum state {
ME = 0, OTHER = 1
};
#define f first
#define s second
typedef long long lli;
typedef pair<int, int> pii;
typedef pair<int, lli> pil;
typedef tuple<int, int, int> tiii;
typedef tuple<lli, int, state, int> tlisi;
const int N = 1e5 + 5;
const int M = 2e5 + 5;
map<int, pil> sum[N];
map<int, lli> distMe[N];
set<int> visitedMe[N];
vector<pii> adj[N];
lli distOther[N];
bool visitedOther[N];
pii edges[M];
void addColorEdge(int u, int c, int w){
map<int, pil>::iterator itr = sum[u].find(c);
if(itr == sum[u].end()){
sum[u][c].f = 1;
sum[u][c].s = w;
} else {
++(itr -> s.f);
itr -> s.s += w;
}
}
int main(){
int nVertex, nEdge;
scanf("%d%d", &nVertex, &nEdge);
for(int i = 1; i <= nEdge; ++i){
int u, v, c, w;
scanf("%d%d%d%d", &u, &v, &c, &w);
edges[i] = pii(c, w);
adj[u].emplace_back(v, i);
adj[v].emplace_back(u, i);
addColorEdge(u, c, w);
addColorEdge(v, c, w);
//printf("edges[%d]: (%d, %d)\n", i, edges[i].f, edges[i].s);
}
for(int u = 1; u <= nVertex; ++u){
distOther[u] = 1e18;
}
priority_queue<tlisi, vector<tlisi>, greater<tlisi>> pq;
distOther[1] = 0;
pq.emplace(distOther[1], 1, OTHER, 0);
while(!pq.empty()){
//printf("dist:%lld\n", get<0>(pq.top()));
int u = get<1>(pq.top());
state us = get<2>(pq.top());
int ui = get<3>(pq.top());
int uc = edges[ui].f;
int uw = edges[ui].s;
//printf("u:%d us:%d ui:%d uc:%d uw:%d\n", u, us, ui, uc, uw);
pq.pop();
if(us == ME){
//printf("ME\n");
if(u == nVertex){
cout << distMe[u][ui];
return 0;
}
if(visitedMe[u].find(ui) != visitedMe[u].end()){
continue;
}
visitedMe[u].insert(ui);
for(pii nxt : adj[u]){
int v = nxt.f;
int i = nxt.s;
int c = edges[i].f;
int w = edges[i].s;
//printf("v:%d c:%d w:%d\n", v, c, w);
//printf("sum[u][c].f:%d\n", sum[u][c].f);
if(sum[u][c].f == 1 || uc == c && sum[u][c].f == 2){
//printf("Change to 0\n");
if(!visitedOther[v] && distMe[u][ui] < distOther[v]){
distOther[v] = distMe[u][ui];
pq.emplace(distOther[v], v, OTHER, i);
}
continue;
}
lli cost = w;
//printf("COST ME:%lld\n", cost);
if(visitedMe[v].find(i) == visitedMe[v].end() && (distMe[v].find(i) == distMe[v].end() || distMe[u][ui] + cost < distMe[v][i])){
distMe[v][i] = distMe[u][ui] + cost;
pq.emplace(distMe[v][i], v, ME, i);
}
cost = sum[u][c].s - w;
if(uc == c){
cost -= uw;
}
//printf("COST OTHER:%lld\n", cost);
if(!visitedOther[v] && distMe[u][ui] + cost < distOther[v]){
distOther[v] = distMe[u][ui] + cost;
pq.emplace(distOther[v], v, OTHER, i);
}
}
} else {
//printf("OTHER\n");
if(u == nVertex){
cout << distOther[u];
return 0;
}
if(visitedOther[u]){
continue;
}
visitedOther[u] = true;
for(pii nxt : adj[u]){
int v = nxt.f;
int i = nxt.s;
int c = edges[i].f;
int w = edges[i].s;
//printf("v:%d\n", v);
if(sum[u][c].f == 1){
//printf("change to 0\n");
if(!visitedOther[v] && distOther[u] < distOther[v]){
distOther[v] = distOther[u];
pq.emplace(distOther[v], v, OTHER, i);
}
continue;
}
lli cost = w;
//printf("COST ME:%lld\n", cost);
if(visitedMe[v].find(i) == visitedMe[v].end() && (distMe[v].find(i) == distMe[v].end() || distOther[u] + cost < distMe[v][i])){
distMe[v][i] = distOther[u] + cost;
pq.emplace(distMe[v][i], v, ME, i);
}
cost = sum[u][c].s - w;
//printf("COST OTHER:%lld\n", cost);
if(!visitedOther[v] && distOther[u] + cost < distOther[v]){
distOther[v] = distOther[u] + cost;
pq.emplace(distOther[v], v, OTHER, i);
}
}
}
}
cout << "-1";
return 0;
}
