#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <complex>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>
using namespace std;
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define SZ(S) ((int) ((S).size()))
#define DEBUG(x) { cout << #x << " = " << x << endl; }
#define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
#define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }
const int INF = 1000000000;
struct Edge {
int a, b, cap, flow;
};
struct MaxFlow {
int n, s, t;
vector<int> d, ptr, q;
vector< Edge > e;
vector< vector<int> > g;
MaxFlow(int n) : n(n), d(n), ptr(n), g(n), q(n) {
e.clear();
REP(i,n) {
g[i].clear();
ptr[i] = 0;
}
}
void addEdge(int a, int b, int cap) {
Edge e1 = { a, b, cap, 0 };
Edge e2 = { b, a, 0, 0 };
g[a].push_back( (int) e.size() );
e.push_back(e1);
g[b].push_back( (int) e.size() );
e.push_back(e2);
}
int getMaxFlow(int _s, int _t) {
s = _s; t = _t;
int flow = 0;
for (;;) {
if (!bfs()) break;
REP(i,n) ptr[i] = 0;
while (int pushed = dfs(s, INF))
flow += pushed;
}
return flow;
}
private:
bool bfs() {
int qh = 0, qt = 0;
q[qt++] = s;
REP(i,n) d[i] = -1;
d[s] = 0;
while (qh < qt && d[t] == -1) {
int v = q[qh++];
REP(i,g[v].size()) {
int id = g[v][i], to = e[id].b;
if (d[to] == -1 && e[id].flow < e[id].cap) {
q[qt++] = to;
d[to] = d[v] + 1;
}
}
}
return d[t] != -1;
}
int dfs (int v, int flow) {
if (!flow) return 0;
if (v == t) return flow;
for (; ptr[v] < (int)g[v].size(); ++ptr[v]) {
int id = g[v][ptr[v]],
to = e[id].b;
if (d[to] != d[v] + 1) continue;
int pushed = dfs(to, min(flow, e[id].cap - e[id].flow));
if (pushed) {
e[id].flow += pushed;
e[id^1].flow -= pushed;
return pushed;
}
}
return 0;
}
};
const int MN = 111;
const int MM = 10111;
const int oo = 1000111000;
int n, m, c[MN][MN];
int eu[MM], ev[MM], ec[MM];
int main() {
ios :: sync_with_stdio(false); cin.tie(NULL);
cout << (fixed) << setprecision(6);
while (cin >> n >> m) {
FOR(i,1,n) FOR(j,1,n) c[i][j] = oo;
FOR(i,1,n) c[i][i] = 0;
FOR(i,1,m) {
int u, v, l; cin >> u >> v >> l;
++u; ++v;
eu[i] = u; ev[i] = v; ec[i] = l;
c[u][v] = min(c[u][v], l);
c[v][u] = c[u][v];
}
FOR(k,1,n) FOR(i,1,n) FOR(j,1,n) c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
if (c[1][n] == oo) {
cout << 0 << endl;
continue;
}
MaxFlow flow(2*n);
FOR(i,1,n) {
int c = (i == 1 || i == n) ? oo : 1;
flow.addEdge(2*i-2, 2*i-1, c);
}
FOR(i,1,m) {
if (c[1][eu[i]] + ec[i] + c[ev[i]][n] == c[1][n])
flow.addEdge(2*eu[i]-1, 2*ev[i]-2, oo);
if (c[1][ev[i]] + ec[i] + c[eu[i]][n] == c[1][n])
flow.addEdge(2*ev[i]-1, 2*eu[i]-2, oo);
}
int res = flow.getMaxFlow(0, 2*n-1);
if (res >= oo) cout << "IMPOSSIBLE" << endl;
else cout << res << endl;
}
return 0;
}
I2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPGxpc3Q+CiNpbmNsdWRlIDxjbWF0aD4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxjc3RkaW8+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxjc3RkbGliPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPHNzdHJlYW0+CiNpbmNsdWRlIDxpb21hbmlwPgojaW5jbHVkZSA8Y29tcGxleD4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKI2luY2x1ZGUgPGN0aW1lPgojaW5jbHVkZSA8ZGVxdWU+CiNpbmNsdWRlIDxiaXRzZXQ+CiNpbmNsdWRlIDxjY3R5cGU+CiNpbmNsdWRlIDx1dGlsaXR5PgojaW5jbHVkZSA8Y2Fzc2VydD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgRk9SKGksYSxiKSBmb3IoaW50IGk9KGEpLF9iPShiKTsgaTw9X2I7IGkrKykKI2RlZmluZSBGT1JEKGksYSxiKSBmb3IoaW50IGk9KGEpLF9iPShiKTsgaT49X2I7IGktLSkKI2RlZmluZSBSRVAoaSxhKSBmb3IoaW50IGk9MCxfYT0oYSk7IGk8X2E7IGkrKykKI2RlZmluZSBFQUNIKGl0LGEpIGZvcihfX3R5cGVvZihhLmJlZ2luKCkpIGl0ID0gYS5iZWdpbigpOyBpdCAhPSBhLmVuZCgpOyArK2l0KQojZGVmaW5lIFNaKFMpICgoaW50KSAoKFMpLnNpemUoKSkpCgojZGVmaW5lIERFQlVHKHgpIHsgY291dCA8PCAjeCA8PCAiID0gIiA8PCB4IDw8IGVuZGw7IH0KI2RlZmluZSBQUihhLG4pIHsgY291dCA8PCAjYSA8PCAiID0gIjsgRk9SKF8sMSxuKSBjb3V0IDw8IGFbX10gPDwgJyAnOyBjb3V0IDw8IGVuZGw7IH0KI2RlZmluZSBQUjAoYSxuKSB7IGNvdXQgPDwgI2EgPDwgIiA9ICI7IFJFUChfLG4pIGNvdXQgPDwgYVtfXSA8PCAnICc7IGNvdXQgPDwgZW5kbDsgfQoKY29uc3QgaW50IElORiA9IDEwMDAwMDAwMDA7CiAKc3RydWN0IEVkZ2UgewogICAgaW50IGEsIGIsIGNhcCwgZmxvdzsKfTsKCnN0cnVjdCBNYXhGbG93IHsKICAgIGludCBuLCBzLCB0OwogICAgdmVjdG9yPGludD4gZCwgcHRyLCBxOwogICAgdmVjdG9yPCBFZGdlID4gZTsKICAgIHZlY3RvcjwgdmVjdG9yPGludD4gPiBnOwoKICAgIE1heEZsb3coaW50IG4pIDogbihuKSwgZChuKSwgcHRyKG4pLCBnKG4pLCBxKG4pIHsKICAgICAgICBlLmNsZWFyKCk7CiAgICAgICAgUkVQKGksbikgewogICAgICAgICAgICBnW2ldLmNsZWFyKCk7CiAgICAgICAgICAgIHB0cltpXSA9IDA7CiAgICAgICAgfQogICAgfQoKICAgIHZvaWQgYWRkRWRnZShpbnQgYSwgaW50IGIsIGludCBjYXApIHsKICAgICAgICBFZGdlIGUxID0geyBhLCBiLCBjYXAsIDAgfTsKICAgICAgICBFZGdlIGUyID0geyBiLCBhLCAwLCAwIH07CiAgICAgICAgZ1thXS5wdXNoX2JhY2soIChpbnQpIGUuc2l6ZSgpICk7CiAgICAgICAgZS5wdXNoX2JhY2soZTEpOwogICAgICAgIGdbYl0ucHVzaF9iYWNrKCAoaW50KSBlLnNpemUoKSApOwogICAgICAgIGUucHVzaF9iYWNrKGUyKTsKICAgIH0KICAgIGludCBnZXRNYXhGbG93KGludCBfcywgaW50IF90KSB7CiAgICAgICAgcyA9IF9zOyB0ID0gX3Q7CiAgICAgICAgaW50IGZsb3cgPSAwOwogICAgICAgIGZvciAoOzspIHsKICAgICAgICAgICAgaWYgKCFiZnMoKSkgYnJlYWs7CiAgICAgICAgICAgIFJFUChpLG4pIHB0cltpXSA9IDA7CiAgICAgICAgICAgIHdoaWxlIChpbnQgcHVzaGVkID0gZGZzKHMsIElORikpCiAgICAgICAgICAgICAgICBmbG93ICs9IHB1c2hlZDsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIGZsb3c7CiAgICB9Cgpwcml2YXRlOgogICAgYm9vbCBiZnMoKSB7CiAgICAgICAgaW50IHFoID0gMCwgcXQgPSAwOwogICAgICAgIHFbcXQrK10gPSBzOwogICAgICAgIFJFUChpLG4pIGRbaV0gPSAtMTsKICAgICAgICBkW3NdID0gMDsKCiAgICAgICAgd2hpbGUgKHFoIDwgcXQgJiYgZFt0XSA9PSAtMSkgewogICAgICAgICAgICBpbnQgdiA9IHFbcWgrK107CiAgICAgICAgICAgIFJFUChpLGdbdl0uc2l6ZSgpKSB7CiAgICAgICAgICAgICAgICBpbnQgaWQgPSBnW3ZdW2ldLCB0byA9IGVbaWRdLmI7CiAgICAgICAgICAgICAgICBpZiAoZFt0b10gPT0gLTEgJiYgZVtpZF0uZmxvdyA8IGVbaWRdLmNhcCkgewogICAgICAgICAgICAgICAgICAgIHFbcXQrK10gPSB0bzsKICAgICAgICAgICAgICAgICAgICBkW3RvXSA9IGRbdl0gKyAxOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiBkW3RdICE9IC0xOwogICAgfQoKICAgIGludCBkZnMgKGludCB2LCBpbnQgZmxvdykgewogICAgICAgIGlmICghZmxvdykgcmV0dXJuIDA7CiAgICAgICAgaWYgKHYgPT0gdCkgcmV0dXJuIGZsb3c7CiAgICAgICAgZm9yICg7IHB0clt2XSA8IChpbnQpZ1t2XS5zaXplKCk7ICsrcHRyW3ZdKSB7CiAgICAgICAgICAgIGludCBpZCA9IGdbdl1bcHRyW3ZdXSwKICAgICAgICAgICAgICAgIHRvID0gZVtpZF0uYjsKICAgICAgICAgICAgaWYgKGRbdG9dICE9IGRbdl0gKyAxKSBjb250aW51ZTsKICAgICAgICAgICAgaW50IHB1c2hlZCA9IGRmcyh0bywgbWluKGZsb3csIGVbaWRdLmNhcCAtIGVbaWRdLmZsb3cpKTsKICAgICAgICAgICAgaWYgKHB1c2hlZCkgewogICAgICAgICAgICAgICAgZVtpZF0uZmxvdyArPSBwdXNoZWQ7CiAgICAgICAgICAgICAgICBlW2lkXjFdLmZsb3cgLT0gcHVzaGVkOwogICAgICAgICAgICAgICAgcmV0dXJuIHB1c2hlZDsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICByZXR1cm4gMDsKICAgIH0KfTsKCmNvbnN0IGludCBNTiA9IDExMTsKY29uc3QgaW50IE1NID0gMTAxMTE7CmNvbnN0IGludCBvbyA9IDEwMDAxMTEwMDA7CmludCBuLCBtLCBjW01OXVtNTl07CmludCBldVtNTV0sIGV2W01NXSwgZWNbTU1dOwoKaW50IG1haW4oKSB7CiAgICBpb3MgOjogc3luY193aXRoX3N0ZGlvKGZhbHNlKTsgY2luLnRpZShOVUxMKTsKICAgIGNvdXQgPDwgKGZpeGVkKSA8PCBzZXRwcmVjaXNpb24oNik7CiAgICB3aGlsZSAoY2luID4+IG4gPj4gbSkgewogICAgICAgIEZPUihpLDEsbikgRk9SKGosMSxuKSBjW2ldW2pdID0gb287CiAgICAgICAgRk9SKGksMSxuKSBjW2ldW2ldID0gMDsKICAgICAgICBGT1IoaSwxLG0pIHsKICAgICAgICAgICAgaW50IHUsIHYsIGw7IGNpbiA+PiB1ID4+IHYgPj4gbDsKICAgICAgICAgICAgKyt1OyArK3Y7CiAgICAgICAgICAgIGV1W2ldID0gdTsgZXZbaV0gPSB2OyBlY1tpXSA9IGw7CiAgICAgICAgICAgIGNbdV1bdl0gPSBtaW4oY1t1XVt2XSwgbCk7CiAgICAgICAgICAgIGNbdl1bdV0gPSBjW3VdW3ZdOwogICAgICAgIH0KICAgICAgICBGT1IoaywxLG4pIEZPUihpLDEsbikgRk9SKGosMSxuKSBjW2ldW2pdID0gbWluKGNbaV1bal0sIGNbaV1ba10gKyBjW2tdW2pdKTsKCiAgICAgICAgaWYgKGNbMV1bbl0gPT0gb28pIHsKICAgICAgICAgICAgY291dCA8PCAwIDw8IGVuZGw7CiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIH0KCiAgICAgICAgTWF4RmxvdyBmbG93KDIqbik7CiAgICAgICAgRk9SKGksMSxuKSB7CiAgICAgICAgICAgIGludCBjID0gKGkgPT0gMSB8fCBpID09IG4pID8gb28gOiAxOwogICAgICAgICAgICBmbG93LmFkZEVkZ2UoMippLTIsIDIqaS0xLCBjKTsKICAgICAgICB9CiAgICAgICAgRk9SKGksMSxtKSB7CiAgICAgICAgICAgIGlmIChjWzFdW2V1W2ldXSArIGVjW2ldICsgY1tldltpXV1bbl0gPT0gY1sxXVtuXSkKICAgICAgICAgICAgICAgIGZsb3cuYWRkRWRnZSgyKmV1W2ldLTEsIDIqZXZbaV0tMiwgb28pOwogICAgICAgICAgICBpZiAoY1sxXVtldltpXV0gKyBlY1tpXSArIGNbZXVbaV1dW25dID09IGNbMV1bbl0pCiAgICAgICAgICAgICAgICBmbG93LmFkZEVkZ2UoMipldltpXS0xLCAyKmV1W2ldLTIsIG9vKTsKICAgICAgICB9CiAgICAgICAgaW50IHJlcyA9IGZsb3cuZ2V0TWF4RmxvdygwLCAyKm4tMSk7CiAgICAgICAgaWYgKHJlcyA+PSBvbykgY291dCA8PCAiSU1QT1NTSUJMRSIgPDwgZW5kbDsKICAgICAgICBlbHNlIGNvdXQgPDwgcmVzIDw8IGVuZGw7CiAgICB9CiAgICByZXR1cm4gMDsKfQoK