#include <fstream>
#include <list>
#include <queue>
#include <climits>

using namespace std;

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

const int nmax=50005, INF=INT_MAX;
int n, m;
int vis[nmax], dist[nmax];

list <pair <int, int> >g[nmax];

struct comparator
{
    bool operator()(const int &a,  const int &b) const
    {
        return dist[a]>dist[b];
    }
};

void read_data()
{
    int i, x, y, c;

    fin>>n>>m;

    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        g[x].push_back(make_pair(y,c));
    }
}
void dijkstra(int node)
{
    priority_queue<int, vector<int>, comparator>pq;
    list <pair <int, int> > :: iterator it;
    int i, new_node, cost;

    for(i=1;i<=n;i++)
        dist[i]=INF;

    vis[node]=1;
    dist[1]=0;

    pq.push(node);

    while(!pq.empty())
    {
        node=pq.top();
        pq.pop();
        vis[node]=0;

        for(it=g[node].begin();it!=g[node].end();it++)
        {
            new_node=(*it).first;
            cost=(*it).second;
            if(dist[new_node]>dist[node]+cost)
            {
                dist[new_node]=dist[node]+cost;
                if(!vis[new_node])
                {
                    pq.push(new_node);
                    vis[new_node]=1;
                }
            }
        }
    }
}
void print()
{
    int i;

    for(i=2;i<=n;i++)
        if(dist[i]==INF)
            fout<<0<<' ';
        else
            fout<<dist[i]<<' ';
}
int main()
{
    read_data();
    dijkstra(1);
    print();
}