#include <fstream>
#include <queue>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int NMAX = 5e4 + 5;

typedef pair < int, int > PII;

int N, M, X, Y, C, dp[NMAX];
bool Sel[NMAX];

priority_queue < PII, vector < PII >, greater < PII > > Q;

vector < PII > G[NMAX];

static inline void Read ()
{
    f.tie(NULL);

    f >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        f >> X >> Y >> C;

        G[X].push_back({C, Y});
    }

    return;
}

static inline void Go (int From)
{
    for(int i = 1; i <= N; ++i)
    {
        dp[i] = -1;

        Sel[i] = false;
    }

    dp[From] = 0;
    Sel[From] = true;

    for(auto it : G[From])
    {
        dp[it.second] = it.first;

        Q.push({dp[it.second], it.second});
    }

    while(!Q.empty())
    {
        while(!Q.empty() && Sel[Q.top().second])
            Q.pop();

        if(Q.empty())
            break;

        int Node = Q.top().second;
        int Cost = Q.top().first;

        Sel[Node] = true;

        Q.pop();

        for(auto it : G[Node])
        {
            int X = it.second;

            if(dp[X] == -1)
            {
                dp[X] = Cost + it.first;

                Q.push({dp[X], X});
            }
            else if(Cost + it.first < dp[X])
            {
                dp[X] = Cost + it.first;

                Q.push({dp[X], X});
            }
        }
    }

    for(int i = 1; i <= N; ++i)
        if(i != From)
            g << ((dp[i] != -1) ? dp[i] : 0) << ' ';

    g << '\n';

    return;
}

int main()
{
    Read();

    Go(1);

    return 0;
}