#include <fstream>
#include <bitset>
#include <list>

#define INF 20005

using namespace std;

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

const int nmax=50005, mmax=250005;
int n, m;
int dist[nmax];
list < pair <int, int> > g[nmax];
bitset<nmax>vis;

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({y,c});
    }
}
void dijkstra(int node)
{
    int i, j, mini, poz_mini;
    list < pair <int, int> > :: iterator it;

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

    dist[node]=0;

    for(i=1;i<=n;i++)
    {
        mini=INF;

        for(j=1;j<=n;j++)
            if(dist[j]<mini && !vis[j])
            {
                mini=dist[j];
                poz_mini=j;
            }

        vis[poz_mini]=1;

        for(it=g[poz_mini].begin();it!=g[poz_mini].end();it++)
        {
            int new_node=(*it).first;
            int cost=(*it).second;

            if(dist[new_node]>dist[poz_mini]+cost)
                dist[new_node]=dist[poz_mini]+cost;
        }
    }
}
void print()
{
    int i;

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