#include <bits/stdc++.h>
using namespace std;
#define inf INT_MAX
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int N, M;
vector <pair<int,int> > l[50005];
priority_queue <pair<int,int> > q;
bool viz[50005];
int cost[50005];

void dijkstra(int nod)
{
    int i, costnodaux, nodaux;
    for(i=1; i<=N; i++)
    {
        cost[i]=inf;
    }
    viz[nod]=1;
    cost[nod]=0;
    q.push({nod, 0});
    while(!q.empty())
    {
        nodaux=q.top().first;
        costnodaux=q.top().second;
        q.pop();
        viz[nodaux]=1;
        for(auto &p : l[nodaux])
        {
                if(cost[p.first]>cost[nodaux]+p.second)
                {
                    cost[p.first]=cost[nodaux]+p.second;
                    q.push({p.first, cost[p.first]});
                }
        }

    }
}

int main()
{
    int i, a, b, c;
    fin >> N >> M;
    for(i=1; i<=M; i++)
    {
        fin >> a >> b >> c;
        l[a].push_back(make_pair(b,c));
    }
    dijkstra(1);
    for(i=2; i<=N; i++)
    {
        fout << cost[i] << " ";
    }
}