#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 = 1e5;
vector<map<int, pair<ll,int>>> colorsum(MN);
vector<vector<pair<int,pair<int,int>>>> neighbors(MN);
vector<ll> dp(MN, LLONG_MAX);
map<int, bool> visited[MN];
struct quadriple{
ll value; //当前的value （cost）
int curr; // node
bool changed; //是否改变
int roadcolor; //来的road的color
ll roadvalue; //来的road的value （cost）
quadriple(ll _value, int _curr, bool _changed, int _roadcolor, ll _roadvalue){
value = _value;
curr = _curr;
changed = _changed;
roadcolor = _roadcolor;
roadvalue = _roadvalue;
}
};
struct cmp {
bool operator ()(quadriple & a, quadriple& b){
if(a.value == b.value) return a.curr > b.curr;
return a.value > b.value;
}
};
void dijkstra(int s) {
priority_queue<quadriple, vector<quadriple>, cmp> pq;
pq.push(quadriple(0,1,false,0,0));
while (!pq.empty()) {
quadriple c = pq.top();
pq.pop();
if(visited[c.curr][c.roadcolor] == false){
visited[c.curr][c.roadcolor] = true;
// dp[c.curr][c.changed] =c.value;
dp[c.curr] = min(dp[c.curr], c.value);
for(auto& [nPos, x]: neighbors[c.curr]){ //first = pos, second.first = color, second.second = num|| (was 'a')
int nColor, nValue;
tie(nColor, nValue) = x;
// if(visited[nPos]) continue;
int num = colorsum[c.curr][nColor].second; //colorsum[c.curr].find(nColor)->second.second;
if(num ==1){ //相同颜色的路径数
pq.push(quadriple(c.value, nPos, false, nColor,0));
}else{
if(c.changed == true){ //来的时候改变了颜色
if(nColor == c.roadcolor){ //来的颜色和去的颜色一样
if(num == 2){
pq.push(quadriple(c.value, nPos, false, nColor,0));
}else{
pq.push(quadriple(c.value+ nValue, nPos, true, nColor, nValue));
ll currsum = colorsum[c.curr][nColor].first - c.roadvalue - nValue;
pq.push(quadriple(c.value + currsum, nPos, false,nColor,0));
}
}else{ ////来的颜色和去的颜色不一样
pq.push(quadriple(c.value+ nValue, nPos, true, nColor,nValue));
ll currsum = colorsum[c.curr][nColor].first - nValue;
pq.push(quadriple(c.value+currsum, nPos, false,nColor,0));
}
}else{ //来的时候未改变了颜色
pq.push(quadriple(c.value+nValue, nPos, true, nColor,nValue));
int currsum = colorsum[c.curr][nColor].first - nValue;
pq.push(quadriple(c.value+currsum, nPos, false,nColor,0));
}
}
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
// freopen("Robot.in", "r", stdin);
// freopen("Robot.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; //presum
colorsum[a][c].second+=1; // num of same color routes
colorsum[b][c].first+=d;
colorsum[b][c].second+=1;
}
dijkstra(0);
cout << ((dp[N] != LLONG_MAX)?dp[N] :-1 )<< endl;
}
