#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <climits>
#define pii pair<int,int>
#define mp make_pair
#define NMAX 50005
using namespace std;

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

int n,m,dist[NMAX];
vector <pii> vecini[NMAX];
priority_queue <pii, vector<pii>, greater<pii>> pq;

void dijkstra (int start)
{
    for(int i=1; i<=n; i++)
    {
        dist[i]=INT_MAX;
    }
    dist[start]=0;
    pq.push(mp(dist[start],start));
    while(!pq.empty())
    {

        int nod=pq.top().second;
        int d=pq.top().first;
        pq.pop();
        if(dist[nod]==d)
        {
            for(auto x : vecini[nod])
            {
                if(dist[x.second]>dist[nod]+x.first && dist[nod]!=INT_MAX)
                {
                    dist[x.second]=dist[nod]+x.first;
                    pq.push(mp(dist[x.second],x.second));
                }

            }
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y,z;
        fin>>x>>y>>z;
        vecini[x].push_back(mp(z,y));
    }
    dijkstra(1);
    for(int i=2; i<=n; i++)
    {
        if(dist[i]==INT_MAX)
            fout<<"0 ";
        else
            fout<<dist[i]<<" ";
    }
    return 0;
}