#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define INF 0x3f3f3f3f

ifstream is("dijkstra.in");
ofstream os("dijkstra.out");

struct Edge {
    int y, cost;
    bool operator < (const Edge &c) const
    {
        return c.cost < cost;
    }
};

int n, m;
vector<int> D;
bool v[50001];
vector<vector<Edge> > G;
priority_queue<Edge> Q;

void Read();
void Dijkstra(int node);
void Write();

int main()
{
    Read();
    Dijkstra(1);
    Write();

    is.close();
    os.close();
    return 0;
}


void Read()
{
    int x, y, cost;
    is >> n >> m;
    G = vector<vector<Edge> >(n + 1);
    D = vector<int>(n + 1, INF);
    for ( int i = 1; i <= m; ++i )
    {
        is >> x >> y >> cost;
        G[x].push_back({y, cost});
    }
}

void Dijkstra(int node)
{
    int x, cost;
    D[node] = 0;
    Q.push({node, 0});
    while ( !Q.empty() )
    {
        x = Q.top().y;
        cost = Q.top().cost;
        Q.pop();
        if ( v[x] )
            continue;
        v[x] = true;
        for ( const auto& y : G[x] )
        {
            if ( D[y.y] > y.cost + cost )
            {
                D[y.y] = y.cost + cost;
                Q.push({y.y, D[y.y]});
            }
        }

        while ( !Q.empty() && v[Q.top().y] )
            Q.pop();
    }
}

void Write()
{
    for ( size_t i = 2; i < D.size(); ++i )
        if ( D[i] == INF )
            os << 0 << ' ';
        else
            os << D[i] << ' ';
}