#include <fstream>
#include <deque>
#include <climits>
FILE*f;
FILE*g;
using namespace std;
deque<int>deque1[50000],deque2[50000],coada;
int al[50001],all[50001],i,j,k,d[50001],n,m,x,y,z,a,da;
int main()
{f=fopen("bellman.in","r");
g=fopen("bellman.out","w");
fscanf(f,"%d%d",&m,&n);
for(i=1;i<=n;i++)
{
    fscanf(f,"%d%d%d",&x,&y,&z);
    deque1[x].push_front(y);
    deque2[x].push_front(z);
}
d[1]=0;
al[1]=1;
all[1]++;
for(i=2;i<=m;i++)
    d[i]=INT_MAX;
coada.push_front(1);
while(!coada.empty())
{a=coada.front();
    for(i=1;i<=deque1[a].size();i++)
        {if(al[deque1[a].front()]==0&&d[deque1[a].front()]>d[a]+deque2[a].front())
        {
            d[deque1[a].front()]=d[a]+deque2[a].front();
            coada.push_back(deque1[a].front());
            all[deque1[a].front()]++;
        }
        deque1[a].push_back(deque1[a].front());
        deque1[a].pop_front();
        deque2[a].push_back(deque2[a].front());
        deque2[a].pop_front();
        }
        coada.pop_front();
        al[a]=0;
        for(i=1;i<=n;i++)
                if(all[i]>=n)
        {
            da=1;
            break;
        }
        if(da==1)
            break;
}
if(da==1)
    fprintf(g,"da");
    else
        for(i=2;i<=m;i++)
        fprintf(g,"%d ",d[i]);
    return 0;
}