#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int inf=0x3fffffff; const int Maxn=1100000; int to[Maxn],nxt[Maxn],first[Maxn],t[Maxn],c[Maxn]; int w[Maxn],too[Maxn],nxtt[Maxn],firstt[Maxn]; int n,m,ti,co,u,v,tot=1,e[Maxn]; int b[Maxn],cur[Maxn],dis[Maxn]; inline void add(int u,int v,int ti,int co) { to[tot]=v; nxt[tot]=first[u]; t[tot]=ti; c[tot]=co; first[u]=tot++; } inline void add(int u,int v,int wi) { too[tot]=v; w[tot]=wi; nxtt[tot]=firstt[u]; firstt[u]=tot++; } void spfa() { queue<int>q; memset(dis,0x3f,sizeof(dis)); memset(e,0,sizeof(e)); q.push(1); dis[1]=0; while(!q.empty()) { int now=q.front(); q.pop(); e[now]=0; for(int i=first[now];i;i=nxt[i]) if(dis[to[i]]>dis[now]+t[i]) { dis[to[i]]=dis[now]+t[i]; if(e[to[i]]==0) { q.push(to[i]); e[to[i]]=1; } } } } bool bfs() { queue<int>q; q.push(1); memset(b,0,sizeof(b)); b[1]=1; while(!q.empty()) { int now=q.front(); q.pop(); for(int i=firstt[now];i;i=nxtt[i]) if(w[i]&&b[too[i]]==0) { b[too[i]]=b[now]+1; q.push(too[i]); } } return b[n]; } int dfs(int root,int flow) { if(root==n) return flow; for(int &i=cur[root];i;i=nxtt[i]) if(b[too[i]]==b[root]+1&&w[i]) { int temp=dfs(too[i],min(w[i],flow)); if(temp) { w[i]-=temp; w[i^1]+=temp; return temp; } } return 0; } int dinic() { int ans=0,temp; while(bfs()) { memcpy(cur,firstt,sizeof(cur)); while(temp=dfs(1,inf)) ans+=temp; } return ans; } int main() { // freopen("test.in","r",stdin); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&u,&v,&ti,&co); add(u,v,ti,co); add(v,u,ti,co); } spfa(); tot=2; for(int i=1;i<=n;i++) for(int j=first[i];j;j=nxt[j]) if(dis[to[j]]==dis[i]+t[j]) { add(i,to[j],c[j]); add(to[j],i,0); } printf("%d\n%d\n",dis[n],dinic()); return 0; }