#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define newl '\n'
const int mod = 1e9+7;
const ll MAX = 0x3f3f3f3f3f3f3f3f;
const int MN = 20;// 1e5;
vector<map<int, pair<int,int>>> colorsum(MN);
vector<vector<pair<int,pair<int,int>>>> neighbors(MN);
vector<ll> dp(MN, MAX);
int visited[MN];
struct quadriple{
ll value;
int curr;
bool changed;
int roadcolor;
int roadvalue;
quadriple(ll _value, int _curr, bool _changed, int _roadcolor, int _roadvalue){
value = _value;
curr = _curr;
changed = _changed;
roadcolor = _roadcolor;
roadvalue = _roadvalue;
}
};
struct cmp {
bool operator ()(quadriple & a, quadriple& b){
return a.value > b.value;
}
};
void dijkstra(int s) {
priority_queue<quadriple, vector<quadriple>, cmp> pq;
pq.push(quadriple(0,0,false,0,0));
while (!pq.empty()) {
quadriple c = pq.top();
pq.pop();
if(visited[c.curr] == false){
visited[c.curr] = true;
if(c.curr == 12){
cout << "here" << endl;
}
dp[c.curr] =c.value;
for(auto& [pos, x]: neighbors[c.curr]){ //first = pos, second.first = color, second.second = num|| (was 'a')
if(pos == 12){
cout << pos << endl;
}
int color, num;
tie(color, num) = x;
if(colorsum[c.curr][color].second ==1){
pq.push(quadriple(c.value, pos, false, 0,0));
}else{
if(c.changed == true){
if(color == c.roadcolor){
int currnum = colorsum[c.curr][color].second-1;
int currsum = colorsum[c.curr][color].first - c.roadvalue;
if(currnum == 1){
pq.push(quadriple(c.value, pos, false, 0,0));
}else{
pq.push(quadriple(c.value+num, pos, true, color,num));
pq.push(quadriple(c.value+currsum-num, pos, false,0,0));
}
}else{
int currsum = colorsum[c.curr][color].first;
pq.push(quadriple(c.value+num, pos, true, color,num));
pq.push(quadriple(c.value+currsum-num, pos, false,0,0));
}
}else{
int currsum = colorsum[c.curr][color].first;
pq.push(quadriple(c.value+num, pos, true,color,num));
pq.push(quadriple(c.value+currsum-num,pos, false,0,0));
}
}
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
//freopen("Robot.in", "r", stdin);
//freopen("nocross.out", "w", stdout);
int N,M,a,b,c,d;
cin >> N >> M;
for(int i=0; i<M; i++){
cin >> a >> b >> c >> d;
a--;
b--;
neighbors[a].push_back(make_pair(b,make_pair(c,d)));
neighbors[b].push_back(make_pair(a,make_pair(c,d)));
colorsum[a][c].first +=d;
colorsum[a][c].second+=1;
colorsum[b][c].first+=d;
colorsum[b][c].second+=1;
}
dijkstra(0);
if(dp[N-1] == MAX){
cout << -1 << endl;
return 0;
}
cout << dp[N-1] << endl;
}
