As a general rule (with lots of exceptions), a word like "not" applies to everything after it in the clause. In this particular case, the word "to" has no meaning that can be negated; it just marks the verb "run" as the infinitive form. So "not" negates "run," whether "to" comes before it or after it. In practice, we interpret sentences like these in a way that makes pragmatic sense based on the context. "He tried {not to / to not} run, but his fear got the better of him"--so he did run, or "He tried {not to / to not} run, and found that he was able to resist"--so he didn't run.
It seems more logical to put "not" right before what it negates, as "tried to not run," but it sounds more idiomatic to me to say "tried not to run" (maybe because of the effects of the old bogus "don't split infinitives" rule).
To negate "tried," you would have to move "not" to the left: "He didn't try to run."