#include <bits/stdc++.h>

#define VMAX 100
#define NMAX 50000
#define LOG 21
#define INF (int)(10e8)
#define MOD 30011
#define ll   long long int


#define NIL 0

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

int n,m;
vector<pair<int,int>> adj[NMAX+1];
vector<int> Q;
ll dist[NMAX+1];

bool cmp(int a,int b)
{
    return dist[a] > dist[b];
}
int main()
{
    fin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin >> x >> y >> c;
        adj[x].push_back({y,c});
    }
    for(int i=2;i<=n;i++)
    {
        dist[i] = INF;
    }
    dist[1]=0;

    Q.push_back(1);
    while(!Q.empty())
    {
        pop_heap(Q.begin(),Q.end(),cmp);
        int x = Q[Q.size()-1];
        Q.pop_back();
        for(auto e : adj[x])
        {
            int to = e.first;
            int c = e.second;
            if(dist[to] > dist[x] + c)
            {
                dist[to] = dist[x] + c;
                Q.push_back(to);
                push_heap(Q.begin(),Q.end(),cmp);
            }
        }
    }
    for(int i=2;i<=n;i++)
    {
        fout << (dist[i]==INF ? 0 : dist[i]) << " ";
    }
}