Best model for Machine Learning
If you use the test set for model selection (it does not matter whether you use some random state, or do hyperparameter tuning) then it is dirty and can no longer be used to predict the prediction performance.

The general workflow you should follow is this:


Split into train and test. Lock "test" in a safe.
Use cross-validation on the train set only to tune parameters.
Fix the hyperparameter to the best setting found. Write them in boldface as 'final parameters' into a stone plate on your wall.
Train a new classifier on the entire training set using exactly these parameters
Get the test set from the safe, and run the classifier on the test set exactly once to get a prediction of how well your classifier is going to work in the future
If the results are substantially worse than those from 2.: panic. It's not going to work.
Optional: If you are confident that hyperparameters do not depend on the data size but that you need every little bit of training data, you could train a classifier on train+test with the in-stone parameters. This is risky though, a you don't have a test set anymore.
Deploy, but monitor that it really performs as good as predicted.


The golden rule is: if you used the test set, you must not change the model anymore. You've got one shot to score.

That is why you split the train set again in CV.