0 1 1
1 2 1
1 3 1
0 0 -1
1 1 -1
2 2 -1

-4
+-++

import sys
from operator import itemgetter
from undirectedgraph import UndirectedGraph
from itertools import combinations, product

STATES = [-1, 1]


class IsingModel():

    def __init__(self, graph, bias):
        self._graph = graph
        self._bias = bias
        self._spin_cache = {}
        self._energy_cache = {}
        self._state = {}
        self._energy = None
        self._root = None

    @classmethod
    def from_string(obj, input):
        graph = UndirectedGraph()
        bias = {}
        i = 0
        valid = True
        for line in input:
            i += 1
            try:
                if line.strip():
                    a, b, weight = line.split()
                    a = int(a)
                    b = int(b)
                    weight = int(weight)
                    if a == b:
                        bias[a] = weight
                    else:
                        graph.add_weighted_edge(a, b, weight)

            except ValueError:
                print('Error parsing input on line {} n {}'.format(i, line))
                valid = False

        if not valid:
            exit()

        return obj(graph, bias)

    def bias(self, node):
        return self._bias.get(node, 0)

    def system_energy(self, state):
        energy = 0

        # sum s_i * h_i
        for i in self._graph.nodes():
            energy += state[i] * self.bias(i)

        # sum s_i * s_j * J_ij
        for i, j in combinations(self._graph.nodes(), 2):
            if self._graph.has_edge(i, j):
                weight = self._graph.weight(i, j)
                energy += state[i] * state[j] * weight
        return energy

    def brute_force_solve(self):
        nodes = self._graph.nodes()
        if nodes:
            self._root = list(nodes)[0]
            results = []
            for state_list in product([-1, 1], repeat=len(nodes)):
                state = dict(zip(nodes, state_list))
                energy = self.system_energy(state)
                results.append((energy, state))
            results.sort(key=itemgetter(0))
            self._state = results[0][1]
            self._energy = results[0][0]
        else:
            self._energy = 0

        return self._energy

    def min_energy(self, node, parent, parent_spin):
        args = (node, parent, parent_spin)
        if args in self._energy_cache:
            return self._energy_cache[args]

        if self._graph.is_leaf(node) and parent != None:
            energies = []
            for spin in STATES:
                energy = spin * self.bias(node)
                energy += spin * parent_spin * self._graph.weight(node, parent)
                energies.append((energy, spin))
            return self._min_cache(args, energies)

        energies = []
        for spin in STATES:
            energy = spin * self.bias(node)
            if parent != None:
                energy += spin * parent_spin * self._graph.weight(node, parent)
            for neighbour in self._graph.neighbours(node):
                if neighbour != parent and neighbour != node:
                    energy += self.min_energy(neighbour, node, spin)
            energies.append((energy, spin))

        return self._min_cache(args, energies)

    def _min_cache(self, key, energies):
        energy, spin = min(energies)
        self._energy_cache[key] = energy
        self._spin_cache[key] = spin
        return energy

    def walk_state(self, node, parent, parent_spin):
        spin = self._spin_cache[(node, parent, parent_spin)]
        self._state[node] = spin
        for child in self._graph.neighbours(node):
            if (child, node, spin) in self._spin_cache:
                self.walk_state(child, node, spin)

    def tree_solve(self):
        nodes = self._graph.nodes()
        if nodes:
            self._root = list(nodes)[0]
            self._energy = self.min_energy(self._root, None, None)
            self.walk_state(self._root, None, None)
        else:
            self._energy = 0
        return self._energy

    def solve(self):
        if self._graph.is_tree():
            self.tree_solve()
        else:
            print("Warning: graph is not a tree brute forcing solution")
            self.brute_force_solve()

    def print_answer(self):
        print(self._energy)
        states = list(self._state.items())
        states.sort()
        symbols = {1: '+', -1: '-'}
        print(''.join([symbols[spin] for _, spin in states]))


if __name__ == '__main__':
    model = IsingModel.from_string(sys.stdin)
    model.solve()
    model.print_answer()

from collections import deque


class UndirectedGraph:
    def __init__(self):
        self._nodes = {}
        self._edges = {}

    def _set_weight(self, a, b, weight):
        self._edges[(a, b)] = weight

    def add_node(self, a):
        if a not in self._nodes:
            self._nodes[a] = set()

    def add_edge(self, a, b):
        self.add_node(a)
        self.add_node(b)
        self._nodes[a].add(b)
        self._nodes[b].add(a)
        if (a, b) not in self._edges:
            self._set_weight(a, b, 0)

    def add_weighted_edge(self, a, b, weight):
        self.add_edge(a, b)
        old = self.weight(a, b)
        self._set_weight(a, b, old + weight)

    def set_weighted_edge(self, a, b, weight):
        self.add_edge(a, b)
        self._set_weight(a, b, weight)

    def neighbours(self, a):
        return self._nodes.get(a, None)

    def weight(self, a, b):
        w = self._edges.get((a, b), None)
        if w != None:
            return w
        return self._edges.get((b, a), None)

    def has_edge(self, a, b):
        return (a, b) in self._edges or (b, a) in self._edges

    def is_tree(self):
        # is tree if fully connected and acyclic
        if len(self._nodes) == 0:
            return False
        root = list(self._nodes.keys())[0]
        parent = {root: None}
        queue = deque()
        queue.append(root)
        while queue:
            node = queue.popleft()
            # check for cycle
            for neighbour in self.neighbours(node):
                if neighbour in parent:
                    if parent[node] != neighbour:
                        return False
                else:
                    parent[neighbour] = node
                    queue.append(neighbour)

        # check fully connected
        return parent.keys() == self._nodes.keys()

    def nodes(self):
        return self._nodes.keys()

    def degree(self, node):
        return len(self._nodes[node])

    def is_leaf(self, node):
        return self.degree(node) == 1