//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "


// CHECK THE LIMITS
typedef long long ll;

const int MOD = 1000000007;
const ll INFLL = 1e18;
const int INF = 1e9;
const int NMAX = 50005;

int gcd(int a, int b) {
  return b ? gcd(b, a%b) : a;
} 

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct NodeDist
{
    int dist, vertex;

    NodeDist(const int &dist, const int &vertex)
    {
        this->dist = dist;
        this->vertex = vertex;   
    }

    bool operator <(const NodeDist &other) const{
        return this->dist > other.dist;
    }
};  

vector<NodeDist> graph[NMAX];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m;
    
    priority_queue<NodeDist> pq;

    fin >> n >> m;
    for(int i = 0; i< m; ++i)
    {
        int x,y,dist;
        fin >> x>> y >> dist;
        x--;y--;
        graph[x].push_back({dist,y});
    }

    vector<int> dist(n+1, INF);

    pq.push({0,0});

    while(!pq.empty())
    {
        int vertexDistance = pq.top().dist, vertex = pq.top().vertex;
        pq.pop();

        if(dist[vertex] != INF)
            continue;
        dist[vertex] = vertexDistance;
        for(auto &child : graph[vertex])
        {
            if(dist[child.vertex] == INF)
            {
                pq.push({vertexDistance + child.dist, child.vertex});
            }
        }
    }

    for(int i =1 ;i <n; ++i)
    {
        fout << (dist[i] == INF ? 0 : dist[i]) << " ";
    }

    return 0;
}