#include "stdafx.h"
#include <vector>

using namespace std;

const char TBD = 2;
char rooms[200000];

struct link{
	link();
	link(int _a, int _b,char _c) :
		a(_a), b(_b), c(_c) {}
	int a;
	int b;
	char c;
};

void find(vector<link>& links, vector<int>& results, int curr_result) {
	if (links.empty()) {
		results.push_back(curr_result);
		return;
	}

	link top = links.back();
	links.pop_back();


	if (rooms[top.a] == TBD && rooms[top.b] == TBD) {
		rooms[top.a] = 0;
		find(links, results, curr_result);

		rooms[top.a] = 1;
		find(links, results, curr_result + 1);
	}
	else if (rooms[top.a] != TBD && rooms[top.b] != TBD) {
		if (rooms[top.a] + rooms[top.b] != top.c)
			return; //Can not happen
		else if (links.empty()) {
			results.push_back(curr_result);
		}
	}
	else if (rooms[top.a] != TBD) { // One end is filled
		rooms[top.b] = !(rooms[top.a]);
		find(links, results, curr_result + rooms[top.b]);
	}
	else {
		rooms[top.a] = !(rooms[top.b]);
		find(links, results, curr_result + rooms[top.a]);
	}
}

int main() {
	vector<link> links;
	vector<int> results;

	int n, m, a, b, c;
	scanf("%d %d", &n, &m);
	int temp_res = n;
	fill(rooms, rooms + n, TBD);

	int unknown = n;
	for (int i = 0; i < m; i++){
		scanf("%d %d %d", &a, &b, &c);

		if (c != 1) {
			rooms[a - 1] = c / 2;
			rooms[b - 1] = c / 2;
			temp_res -= c;
		}
		else {
			links.push_back(link(a-1, b-1,c));
			rooms[a - 1] = TBD;
			rooms[b - 1] = TBD;
		}
	}

	find(links, results, temp_res);

	if (results.empty()) {
		printf("impossible");
	}
	return 0;
}