#include <fstream>
#include <vector>
#define NMAX 50005
#define M 250005
#define INF 9999999
using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

int n,m;
//int cost[1001][1001];
int d[NMAX];
int c[5*NMAX],a;
int p,u;

vector <pair<int,int> > cost[M];

void belf(int nod)
{
    for(int i=1;i<=n;i++)
        d[i]=INF;
    d[nod]=0;
    p=u=1;
    c[u]=nod;
    while(p<=u)
    {
        int j=c[p];
        p++;
        for(int i=0;i<cost[j].size();i++)
           // if(cost[j][i].second!=INF)
        {
            a=cost[j][i].first;
            if(d[a]>d[j]+cost[j][i].second)
            {
                d[a]=d[j]+cost[j][i].second;
                c[++u]=a;
            }
        }
    }
}

int main()
{
   f>>n>>m;

   for(int i=1;i<=m;i++)
   {
       int x,y,z;
       f>>x>>y>>z;
       cost[x].push_back(make_pair(y,z));

   }
   belf(1);
   for(int i=2;i<=n;i++)
   if(d[i]==INF)
    g<<0<<" ";
    else
    g<<d[i]<<" ";
   f.close();
   g.close();
    return 0;
}