Description

Elaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等 等，不过到目前为止，他

坚持下来的只有晨跑。 现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从 一

个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天从寝室出发 跑到学校，保证寝室

编号为1，学校编号为N。 Elaxia的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的路线，所以

在一个周期内，每天的晨跑路线都不会相交（在十字路口处），寝室和学校不算十字路 口。Elaxia耐力不太好，

他希望在一个周期内跑的路程尽量短，但是又希望训练周期包含的天 数尽量长。 除了练空手道，Elaxia其他时间

都花在了学习和找MM上面，所有他想请你帮忙为他设计 一套满足他要求的晨跑计划。

Input

第一行：两个数N,M。表示十字路口数和街道数。

接下来M行，每行3个数a,b,c，表示路口a和路口b之间有条长度为c的街道（单向）。

N ≤ ，M ≤ 。

Output

两个数，第一个数为最长周期的天数，第二个数为满足最长天数的条件下最短的路程长 度。

Sample Input

Sample Output

HINT

Source

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

#define duke(i,a,n) for(int i = a;i <= n;i++)

#define lv(i,a,n) for(int i = a;i >= n;i--)

#define clean(a) memset(a,0,sizeof(a))

const int INF =  << ;

typedef long long ll;

typedef double db;

template <class T>

void read(T &x)

{

    char c;

    bool op = ;

    while(c = getchar(), c < '' || c > '')

        if(c == '-') op = ;

    x = c - '';

    while(c = getchar(), c >= '' && c <= '')

        x = x *  + c - '';

    if(op) x = -x;

}

template <class T>

void write(T x)

{

    if(x < ) putchar('-'), x = -x;

    if(x >= ) write(x / );

    putchar('' + x % );

}

const int N = ;

struct node

{

    int l,r,c,f,nxt,other;

}a[N * ];

int len = ,lst[N],st,ed;

void add(int x,int y,int f,int c)

{

    int k1,k2 = ;

    a[++len].l = x;

    a[len].r = y;

    a[len].c = c;

    a[len].f = f;

    a[len].nxt = lst[x];

    lst[x] = len;

    k1 = len;

    a[++len].l = y;

    a[len].r = x;

    a[len].c = -c;

    a[len].f = ;

    a[len].nxt = lst[y];

    lst[y] = len;

    k2 = len;

    a[k1].other = k2;

    a[k2].other = k1;

}

int n,m,dis[N],flow[N],vis[N];

int pre[N],head[N],ans1 = ,ans2 = ;

queue <int> qu;

bool spfa()

{

    clean(vis);

    memset(dis,,sizeof(dis));

    memset(flow,,sizeof(flow));

    memset(pre,,sizeof(pre));

    qu.push(st);

    vis[st] = ;

    dis[st] = ;

    pre[st] = ;

    while(!qu.empty())

    {

        int x = qu.front();

        qu.pop();

        for(int k = lst[x];k;k = a[k].nxt)

        {

            if(a[k].f == )continue;

            int y = a[k].r;

            if(dis[y] > dis[x] + a[k].c)

            {

                dis[y] = dis[x] + a[k].c;

                pre[y] = x;head[y] = k;

                flow[y] = min(flow[x],a[k].f);

                if(!vis[y])

                vis[y] = ,qu.push(y);

            }

        }

        vis[x] = ;

    }

    return pre[ed];

}

void mvp()

{

//    cout<<"QAQ"<<endl;

    int x = flow[ed];

    int i = head[ed];

    ans1 ++;

    /*duke(j,1,2 * n)

    printf("%d ",head[j]);*/

    i = head[ed];

    while(i)

    {

//        cout<<i<<endl;

        ans2 += x * a[i].c;

        a[i].f -= x;

        a[a[i].other].f += x;

        i = head[a[i].l];

//        cout<<a[i].l<<endl;

    }

}

int main()

{

    read(n);read(m);

    st = ;ed = n * ;

    duke(i,,m)

    {

        int u,v,w;

        read(u);read(v);read(w);

        add(u + n,v,,w);

    }

    head[a[].l] = ;

    duke(i,,n - )

    add(i,i + n,,);

    add(,st + n,INF,);

    add(n,ed,INF,);

    while(spfa()) mvp();

    printf("%d %d\n",ans1,ans2);

    return ;

}

/*

7 10

1 2 1

1 3 1

2 4 1

3 4 1

4 5 1

4 6 1

2 5 5

3 6 6

5 7 1

6 7 1

*/