#include<bits/stdc++.h>
using namespace std;
const int MX = 2004;
const long long INF = 1e18;
vector<int>g[MX];
long long cost[MX], color[MX];
int edge[2][MX];
map<int,long long>sum[MX];
void PlayGround() {
int n, m;
cin>>n>>m;
for(int i=1; i<=m; ++i) {
int u, v, c, p;
cin>>u>>v>>c>>p;
color[i] = c, cost[i] = p;
edge[0][i] = u, edge[1][i] = v;
sum[u][c] += p;
sum[v][c] += p;
g[u].push_back(i);
g[v].push_back(i);
}
long long ans[n+1][m+1];
for(int i=0; i<=n; ++i) {
for(int j=0; j<=m; ++j) {
ans[i][j] = INF;
}
}
bool vis[n+1][m+1];
memset(vis, 0, sizeof vis);
priority_queue<tuple<long long, int, int>>pq;
pq.emplace(0, 1, 0);
ans[1][0] = 0;
while(!pq.empty()) {
int v = get<1>(pq.top());
int nerfed = get<2>(pq.top());
pq.pop();
if(vis[v][nerfed]) continue;
vis[v][nerfed] = 1;
for(auto e : g[v]) {
int to = edge[(edge[0][e]==v)][e];
long long cur = cost[e] + ans[v][nerfed];
if(ans[to][e]>cur) {
ans[to][e] = cur;
pq.emplace(-cur, to, e);
}
cur = sum[v][color[e]] - cost[e] + ans[v][nerfed];
if(color[nerfed]==color[e]) cur -= cost[nerfed];
if(ans[to][0]>cur) {
ans[to][0] = cur;
pq.emplace(-cur, to, 0);
}
}
}
long long best = INF;
for(int i=0; i<=m; ++i) {
best = min(best, ans[n][i]);
}
if(best==INF) best = -1;
cout<<best<<'\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
PlayGround();
return 0;
}
