Use tf.nn.sparse_softmax_cross_entropy_with_logits, but beware that it can't accept the output of tf.nn.softmax. Instead, calculate the unscaled activations, and then the cost:
logits = tf.matmul(state_below, U) + b
cost = tf.nn.sparse_softmax_cross_entropy_with_logits(logits, labels)
In this c...