#include <bits/stdc++.h>
#define DIM 100010
using namespace std;
typedef long long ll;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int NMax = 50005;
const int INF = 0x3f3f3f3f;

vector <pair<int,int>> v[NMax];
int dist[NMax];
int main()
{
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        fin>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
    }
    memset(dist,INF,sizeof(dist));
    dist[1] = 0;
    set<pair<int,int>> h;
    h.insert(make_pair(1,0));
    while(!h.empty())
    {
        int node = h.begin()->first;
        int d = h.begin()->second;
        h.erase(h.begin());
    for(vector <pair<int,int>> :: iterator it = v[node].begin();it!=v[node].end();++it)
    {
        int to,cost;
        to = it->first;
        cost = it->second;
        if(dist[to] > dist[node]+cost)
            {
                if(dist[to]!=INF)
                {
                    h.erase(h.find(make_pair(to,dist[to])));
                }
                dist[to] = dist[node]+cost;
                h.insert(make_pair(to,dist[to]));
            }
    }
    }
    for(int i=2;i<=n;i++)
        {if(dist[i]==INF)
        dist[i] = 0;
        fout<<dist[i]<<" ";}
    return 0;
}