#include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <queue>

 using namespace std;

 const int maxn = 2e2 + ;

 const int maxm = 2e4 + ;

 const int inf = 0x3f3f3f3f;

 struct MCMF

 {

     struct Edge

     {

         int v, c, w, next;

     }p[maxm << ];

     int e, head[maxn], dis[maxn], pre[maxn], cnt[maxn], sumFlow, n;

     bool vis[maxn];

     void init(int nt)

     {

         e = , n = nt;

         memset(head, -, sizeof(head[]) * (n + ) );

     }

     void addEdge(int u, int v, int c, int w)

     {

         p[e].v = v, p[e].c = c; p[e].w = w; p[e].next = head[u]; head[u] = e++;

         swap(u, v);

         p[e].v = v, p[e].c = ; p[e].w = -w; p[e].next = head[u]; head[u] = e++;

     }

     bool spfa(int S, int T)

     {

         queue <int> q;

         for (int i = ; i <= n; ++i)

             vis[i] = cnt[i] = , pre[i] = -, dis[i] = inf;

         vis[S] = , dis[S] = ;

         q.push(S);

         while (!q.empty())

         {

             int u = q.front(); q.pop();

             vis[u] = ;

             for (int i = head[u]; i + ; i = p[i].next)

             {

                 int v = p[i].v;

                 if (p[i].c && dis[v] > dis[u] + p[i].w)

                 {

                     dis[v] = dis[u] + p[i].w;

                     pre[v] = i;

                     if (!vis[v])

                     {

                         q.push(v);

                         vis[v] = ;

                         if (++cnt[v] > n) return ;

                     }

                 }

             }

         }

         return dis[T] != inf;

     }

     int mcmf(int S, int T)

     {

         sumFlow = ;

         int minFlow = , minCost = ;

         while (spfa(S, T))

         {

             minFlow = inf + ;

             for (int i = pre[T]; i + ; i = pre[ p[i ^ ].v ])

                 minFlow = min(minFlow, p[i].c);

             sumFlow += minFlow;

             for (int i = pre[T]; i + ; i = pre[ p[i ^ ].v ])

             {

                 p[i].c -= minFlow;

                 p[i ^ ].c += minFlow;

             }

             minCost += dis[T] * minFlow;

         }

         return minCost;

     }

     void build(int nt, int mt)

     {

         init((nt << ) + );

         int u, v, c;

         for (int i = ; i <= nt; ++i)

         {

             addEdge(, i, , );

             addEdge(i + nt, n, , );

         }

         while (mt--)

         {

             scanf("%d%d%d", &u, &v, &c);

             addEdge(u, v + nt, , c);

         }

     }

     void solve(int nt)

     {

         int ans = mcmf(, n);

         if ( sumFlow != nt)

             printf("-1\n");

         else

             printf("%d\n", ans);

     }

 }my;

 int main()

 {

     int n, m;

     while (~scanf("%d%d", &n, &m))

     {

         my.build(n, m);

         my.solve(n);

     }

     return ;

 }