#include <fstream>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;

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


struct Edge{
    int first, second;
    const bool operator < (const Edge& other) const
    {
        return second > other.second;
    }
};
int n, m;
vector<vector<pair <int, int> > > g;
vector<int> d;
vector<bool> s;

priority_queue<Edge> heap;

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

int main()
{
    Read();
    Dijkstra(1);
    Write();
    is.close();
    os.close();
    return 0;
}

void Read()
{
    is >> n >> m;
    int x, y, z;
    g = vector <vector<pair<int, int>>>(n+1);
    d = vector <int>(n+1, INF);
    s = vector <bool>(n+1);
    for(int i = 1; i <= m; ++i)
    {
        is >> x >> y >> z;
        g[x].push_back({y, z});
    }

}
 void Dijkstra(int k)
{
    d[k] = 0;
    s[k] = true;
    heap.push({k, 0});
    while(!heap.empty())
    {
        k = heap.top().first;
        s[k] = true;
        for(const auto y: g[k])
        {
            if(!s[y.first] && d[k] + y.second < d[y.first])
            {
                d[y.first] = d[k] + y.second;
                heap.push({y.first, d[y.second]});
            }
        }
        while(!heap.empty() && s[heap.top().first])
            heap.pop();
    }

}

void Write()
{
    for(int i = 2; i <= n; ++i)
    {
        if(d[i] == INF)
            os << 0 << ' ';
        else
            os << d[i] << ' ';
    }
    return;
}